You do not have permission to edit this page, for the following reason:
You can view and copy the source of this page.
Templates used on this page:
Return to GATE2009 q3.
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