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

6,730 views

## 5 Answers

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).

### 4 Comments

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

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.