retagged by
996 views

4 Answers

Best answer
2 votes
2 votes

Proof by contradiction:

In a simple graph of $n$ vertices,

Minimum degree possible $=0$

Maximum degree possible $ = n-1$

Assume that all $n$ vertices of the graph have different degrees. It implies that we enumerate all vertices uniquely with their degrees from $0$ to $n-1$. But since vertices with degrees $0$ and $n - 1$ cannot co-exist in a simple graph, it results in a contradiction.

Therefore, atleast two vertices must have the same degree.

selected by
1 votes
1 votes
Lets take graph with 3 vertices $v _1, v_2, v_3$. now assign different degree to each vertex for $d( v _1)=0$ , $d(v _2)=1$ ,$d(v_3)= 2$, now use handshaking theorem that is $2*edge=$ $sum$ $of$ $the$ $degree$ $of$ $each$ $ vertex$ , which also conclude that sum of degrees of vertices should be even

now , add each  degree of each vertices that is $ \Rightarrow 0+1+2 =3$ (which is not even) to make this even u have to make $v _3=1$ , or $v _1=1,v _2=1,v _3=2$  or   $v  _1=0,v _2=0,v _3=0$ and so many possibilities

now if some people argue for $v _1=2,v _2=3,v _3=5$ , for that we cant tale such example for 3 vertices graph because simple graph(no loop and parallel edges) is given.
edited by
0 votes
0 votes
Think the question using pigeon hole principle.

If a simple graph has n vertices , the possible degrees are among  [0,1,2,...n-1]. And second thing is that if you have a vertex with degree n-1 then , you cannot have a isolated vertex (whose degree is 0) . So a vertex with degree n-1 and degree 0 is not possible together if a graph has n vertices . So let's assume there is no isolated vertex .

So, degree sequence should be among [1,2,...n-1], and you have n vertices , try to assign every vertex with distinct degree , then only you can satisfy upto n-1 vertices but for nth vertex you have to choose one of the values that you have already choosen ( similar to pigeon hole principle , if you have k pigeons and k-1 holes then atleast 2 pigeons have to sit in same hole ).

I hope it is clear. Same can be proved if you have isolated vertex by taking that there is no degree n-1 vertex.

Related questions