in Graph Theory retagged by
39 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.
in Graph Theory retagged by


Although people have given very good answer but same thing could be proved using graphic sequence.

Previous year question concept used here:

Means repeated?

Subscribe to GO Classes for GATE CSE 2022

5 Answers

67 votes
Best answer

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


Take a connected graph of 4 vertices and 5 edges ... U will get B as answer ...
Every graph with n$\geq$2 has a spanning tree T.

In this spanning Tree  T of a graph, we do have an open path which covers all vertices of G.

The terminal vertices of a path are of degree one hence the proof.
we can't represent any degree sequence where all degrees are unique. at least on degree should be repeated which means at least two vertices have same degree.
6 votes
Now concentrate on two vertices suppose there is no edge between then it has degree 0 each ,when edge is present then 1 if you with the edges a bit you will come to the conclusion that atleast two vertices have same degree
4 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
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
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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true