retagged by
11,272 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

1 votes
1 votes
Method 1:
If all vertices have different degrees, then the degree sequence will be {1,2,3,....n-1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n-1) vertices). Degree sequence has only (n-1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) consider a triangle, all vertices has same degree, so it is false
C) consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
0 votes
0 votes
proof by contradiction-

when no.of vertices =3,now we can take degree 0,1,2 to 3 vertices but as graph is connected no vertex can take degree 0,so it must take either degree 1 or 2
0 votes
0 votes

Since it’s mentioned in question that, any simple connected undirected graph with more than 2 vertices

 we can see that only two edges are enough for connectivity.

So Option B is true

i,e At least two vertices have the same degree is TRUE. 

Answer:

Related questions

49 votes
49 votes
11 answers
1
gatecse asked Sep 15, 2014
13,016 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