GATE2010 q28 - Revision history

Arjun Suresh at 11:37, 15 July 2014

2014-07-15T11:37:43Z

Arjun Suresh at 14:28, 14 July 2014

2014-07-14T14:28:40Z

Arjun Suresh at 23:04, 13 July 2014

2014-07-13T23:04:32Z

Arjun Suresh at 22:50, 13 July 2014

2014-07-13T22:50:20Z

Arjun Suresh at 11:36, 30 June 2014

2014-06-30T11:36:36Z

Arjun Suresh at 11:36, 30 June 2014

2014-06-30T11:36:02Z

Arjun Suresh at 14:38, 29 June 2014

2014-06-29T14:38:08Z

Arjun Suresh at 14:18, 29 June 2014

2014-06-29T14:18:48Z

Arjun Suresh at 13:45, 29 June 2014

2014-06-29T13:45:45Z

Arjun Suresh at 13:43, 29 June 2014

2014-06-29T13:43:45Z

← Older revision		Revision as of 11:37, 15 July 2014
Line 43:		Line 43:

	[[Category: GATE2010]]		[[Category: GATE2010]]
−	[[Category: Graph Theory questions]]	+	[[Category: Graph Theory questions from GATE]]

← Older revision		Revision as of 14:28, 14 July 2014
Line 1:		Line 1:
−	The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not	+	The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
−	be the degree sequence of any graph?

	I. $7, 6, 5, 4, 4, 3, 2, 1$		I. $7, 6, 5, 4, 4, 3, 2, 1$

← Older revision		Revision as of 23:04, 13 July 2014
Line 45:		Line 45:
	[[Category: GATE2010]]		[[Category: GATE2010]]
	[[Category: Graph Theory questions]]		[[Category: Graph Theory questions]]
−	~~[[Category:Discrete Mathematics questions ]]~~

@@ Line 42: / Line 42: @@
 {{Template:FBD}}
-[[Category:Graph Theory]]
 [[Category: GATE2010]]
 [[Category: Graph Theory questions]]
 [[Category:Discrete Mathematics questions ]]

@@ Line 37: / Line 37: @@
 			negative, this degree sequence is not possible.</li>
 		</ol>
-		Since (II) comes only in option <b>(A)</b> and <b>(D)</b>, and since <b>(A)</b> contains I, which is correct degree
+		Since '''(II)''' comes only in option <b>(A)</b> and <b>(D)</b>, and since <b>(A)</b> contains '''I''', which is correct degree
 		sequence, <b>(D)</b> must be right answer. We don't need to check for other sequences.

@@ Line 33: / Line 33: @@
 			<li>$7, 6, 5, 4, 4, 3, 2, 1$. Here first vertex has degree $7$, so remove this first vertex, and then subtract $1$ from next $7$
 			vertices, so we get $5,4,3,3,2,1,0$. Then we get $3,2,2,1,0,0$ then $1,1,0,0,0$ and then $0,0,0,0$. So, answer is yes.</li>
 		</ol>
-		Since (I) comes only in one option i.e. option <b>(A)</b>, it is correct answer. We don't need to check for other sequences.
+		Since (II) comes only in option <b>(A)</b> and <b>(D)</b>, and since <b>(A)</b> contains I, which is correct degree
 {{Template:FBD}}

@@ Line 40: / Line 40: @@
 [[Category: GATE2010]]
 [[Category: Graph Theory questions]]
-[[Category:Mathematics Questions from GATE]]
+[[Category:Discrete Mathematics Questions from GATE]]

@@ Line 29: / Line 29: @@
 			step 2.</li>
 		</ol>
-		So we check each degree sequence given in question :
+		So, we check each degree sequence given in question :
 		<ol>
 			<li>$7, 6, 5, 4, 4, 3, 2, 1$. Here first vertex has degree $7$, so remove this first vertex, and then subtract $1$ from next $7$
-			vertices, so we get $5,4,3,3,2,1,0$. Then we get $3,2,2,1,0,0$ then $1,1,0,0,0$ and then $0,0,0,0$. So answer is yes.</li>
+			vertices, so we get $5,4,3,3,2,1,0$. Then we get $3,2,2,1,0,0$ then $1,1,0,0,0$ and then $0,0,0,0$. So, answer is yes.</li>
 		</ol>
 		Since (I) comes only in one option i.e. option <b>(A)</b>, it is correct answer. We don't need to check for other sequences.

@@ Line 2: / Line 2: @@
 		be the degree sequence of any graph?
-		I. 7, 6, 5, 4, 4, 3, 2, 1
+		I. $7, 6, 5, 4, 4, 3, 2, 1$
-		II. 6, 6, 6, 6, 3, 3, 2, 2
+		II. $6, 6, 6, 6, 3, 3, 2, 2$
-		III. 7, 6, 6, 4, 4, 3, 2, 2
+		III. $7, 6, 6, 4, 4, 3, 2, 2$
-		IV. 8, 7, 7, 6, 4, 2, 1, 1
+		IV. $8, 7, 7, 6, 4, 2, 1, 1$
@@ Line 24: / Line 24: @@
 		<ol>
 			<li>First arrange degree sequence in decreasing order.</li>
-			<li>Remove 1st vertex, and let its degree be k, then subtract 1 from next k vertices.</li>
+			<li>Remove $1^{st}$ vertex, and let its degree be $k$, then subtract $1$ from next $k$ vertices.</li>
-			<li>If all vertices have degree 0, then answer is yes i.e. given degree seqeunce can be a degree sequence for a graph.
+			<li>If all vertices have degree $0$, then answer is yes i.e. given degree sequence can be a degree sequence for a graph.
-			If any vertex has degree &lt; 0, then answer is no, otherwise repeat
+			If any vertex has degree &lt; $0$, then answer is no, otherwise repeat
 			step 2.</li>
 		</ol>
 		So we check each degree sequence given in question :
 		<ol>
-			<li>7, 6, 5, 4, 4, 3, 2, 1. Here first vertex has degree 7, so remove this first vertex, and then subtract 1 from next 7
+			<li>$7, 6, 5, 4, 4, 3, 2, 1$. Here first vertex has degree $7$, so remove this first vertex, and then subtract $1$ from next $7$
-			vertices, so we get 5,4,3,3,2,1,0. Then we get 3,2,2,1,0,0, then 1,1,0,0,0, and then 0,0,0,0. So answer is yes.</li>
+			vertices, so we get $5,4,3,3,2,1,0$. Then we get $3,2,2,1,0,0$ then $1,1,0,0,0$ and then $0,0,0,0$. So answer is yes.</li>
 		</ol>
 		Since (I) comes only in one option i.e. option <b>(A)</b>, it is correct answer. We don't need to check for other sequences.