Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 28: | Line 28: | ||
[[Category: GATE2009]] | [[Category: GATE2009]] | ||
| − | [[Category: Graph Theory questions]] | + | [[Category: Graph Theory questions from GATE]] |
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.
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.
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.
So, option (B) is correct.
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.
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.
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.
So, option (B) is correct.
GATECSE