Register

GATE CSE 2009 | Question: 3

• retagged by
18,725 views
73 73 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.

8 Answers

Best answer
103 103 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
21 21 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. 

8 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
6 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
4 4 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.
1 1 vote
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
Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2009 | Ques...Next → · GATE CSE 2002 | Ques...
← Previous in category · GATE CSE 2009 | Ques...Next in category → · GATE CSE 2002 | Ques...
Position:
Show:

Related questions

63 63 votes
11 answers 11 answers
24.3k
24.3k views
gatecse asked Sep 15, 2014
24,307 views
GATE CSE 2009 | Question: 2
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$
8 8 votes
1 answers 1 answer
3.8k
3.8k views
go_editor asked Jun 15, 2016
3,808 views
ISRO CSE 2009 | Question: 52
If $\text{G}$ is a graph with e edges and n vertices the sum of the degrees of all vertices in $\text{G}$ is$e$$e/2$$e^2$$2 e$
140 140 votes
7 answers 7 answers
29.3k
29.3k views
go_editor asked Apr 24, 2016
29,287 views
GATE CSE 2006 | Question: 72
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets...
50 50 votes
5 answers 5 answers
14.5k
14.5k views
go_editor asked Sep 28, 2014
14,501 views
GATE CSE 2014 | Set 1 | Question: 52
An ordered $n-$tuple $(d_1, d_2,\ldots,d_n)$ with $d_1 \geq d_2 \geq \ldots \geq d_n$ is called graphic if there exists a simple undirected graph with $n$ vertices havin...