Difference between revisions of "GATE2009 q3"

Latest revision as of 11:38, 15 July 2014

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.

Solution by Happy Mittal

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.