GATE2009 q3 - Revision history

Arjun Suresh at 11:38, 15 July 2014

2014-07-15T11:38:08Z

Arjun Suresh at 23:03, 13 July 2014

2014-07-13T23:03:14Z

Arjun Suresh at 22:49, 13 July 2014

2014-07-13T22:49:27Z

Arjun Suresh at 16:09, 29 June 2014

2014-06-29T16:09:39Z

Arjun Suresh: Created page with " Which one of the following is '''TRUE''' for any simple connected undirected graph with more than $2$ vertices? (A) No two vertices have the same degree. '''(B) At least ..."

2014-06-29T16:09:22Z

Created page with " Which one of the following is '''TRUE''' for any simple connected undirected graph with more than $2$ vertices? (A) No two vertices have the same degree. '''(B) At least ..."

New page

Which one of the following is '''TRUE''' for any simple connected undirected graph
with more than $2$ vertices?

(A) No two vertices have the same degree.

'''(B) At least two vertices have the same degree.'''

(C) At least three vertices have the same degree.

(D) All vertices have the same degree.

==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
We argue that "At least two vertices have the same degree". Let us see why. If that is not true i.e., if all $n$ vertices
have different degrees, then degrees must be $0,1,2...,n-1$, we can't have a degree > $n-1$, because there are only $n$ vertices and graph
is simple i.e., has no self loops.
<br>
But this degree sequence $0,1,2,...,n-1$ is not possible, because it means there is a vertex with $0$ degree (not connected to any
vertex), and there is a vertex with $n-1$ degree (connected to every vertex), which is not possible simultaneously.
<br>
So option <b>(B)</b> is correct.

{{Template:FBD}}

[[Category: Graph Theory]]
[[Category: GATE2009]]
[[Category: Graph Theory questions]]
[[Category:Discrete Mathematics questions]]

← Older revision		Revision as of 11:38, 15 July 2014
Line 28:		Line 28:

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

← Older revision		Revision as of 23:03, 13 July 2014
Line 29:		Line 29:
	[[Category: GATE2009]]		[[Category: GATE2009]]
	[[Category: Graph Theory questions]]		[[Category: Graph Theory questions]]
−	~~[[Category:Discrete Mathematics questions]]~~

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

@@ Line 22: / Line 22: @@
 		vertex), and there is a vertex with $n-1$ degree (connected to every vertex), which is not possible simultaneously.
 		<br>
-		So option <b>(B)</b> is correct.
+		So, option <b>(B)</b> is correct.
 {{Template:FBD}}