retagged by
11,266 views
54 votes
54 votes

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

  1.    No two vertices have the same degree.
  2.    At least two vertices have the same degree.
  3.    At least three vertices have the same degree.
  4.    All vertices have the same degree.
retagged by

7 Answers

Best answer
80 votes
80 votes

answer = option (B)

There are $n$ vertices and at least $\left(n-1\right)$ edges. So, for each vertex, degree should range from $1$ (since graph is connected) to $\left(n-1\right)$ (since graph is simple).

But we have $n$ such vertices- filling $n$ things with $\left(n-1\right)$ numbers.

$\bigg \lceil \frac{n}{n-1} \bigg\rceil = \lceil 1.\sim \rceil = 2$ 

So, at least $2$ of them must be equal (pigeonhole principle).

edited by
8 votes
8 votes
Now concentrate on two vertices suppose there is no edge between then it has degree 0 each ,when edge is present then 1 each..now if you with the edges a bit you will come to the conclusion that atleast two vertices have same degree
7 votes
7 votes

Simpler way:-

Let’s take n=3.

Since it’s mentioned in question that, any simple connected undirected graph with more than 2 vertices in fig 1, it’s disconnected. So it’s wrong.

In Fig 2, we can see that only two edges are enough for connectivity. So Option B, i,e At least two vertices have the same degree is TRUE. 

Rest of the options are automatically false using this example. 

6 votes
6 votes
lets take graph with 3 vertices , v1,v2,v3 , now assign different degree to each vertices for d(v1)=0 , d(v2)=1 ,d(v3)=2 , now use handshaking theoram that is 2*edge=sum of degree of each vertices , which also conclude that sum of degrees of vertices should be even

 

now , add each  degree of each vertices that is = 0+1+2 =3(which is not even) to make this even u have to make v3=1 , or v1=1,v2=1,v3=2 or v1=0,v2=0,v3=0 and so many possibilities

now if some people argue for v1=2,v2=3,v3=5 , for that we cant tale such example for 3 vertices graph because simple graph(no loop and parallel edges) is given
Answer:

Related questions

49 votes
49 votes
11 answers
1
gatecse asked Sep 15, 2014
13,002 views
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n 2$.$2$$3$$n-1$ $n$
65 votes
65 votes
4 answers
4