Dark Mode

8,376 views

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

5

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

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

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