retagged by
4,291 views
48 votes
48 votes
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.
retagged by

3 Answers

Best answer
83 votes
83 votes
Let $n>2$ and all the vertices have distinct degrees. Now, let the degrees be $0, 1, 2, \dots ,\left(n-1\right)$ which are all distinct and possible as a vertex can be connected to $\left(n-1\right)$ other vertices. But, there is a problem here if a vertex is connected to $\left(n-1\right)$ other vertices, it means there cannot be a vertex with $0$ degree anymore. Thus for $n$ vertices we now have only$\left(n-1\right)$ possible degrees meaning at least one must repeat- pigeon comes here :)
edited by
33 votes
33 votes

Let us assume a graph with $n>2$ vertices exists and it is such that each of its vertex is assigned a distinct degree.

To assign each vertex a distinct degree we need a set of n numbers.

We cannot start count from $1$, coz then it will go up to vertex degree $n$ but the graph is a simple graph and it rules out the possibility to have self loops and parallel edges; Without them a vertex with degree n is not possible.

so we have a n-element set = [0,n-1]

a vertex with a degree $0$ means that one of the vertex is disconnected 
a vertex with a degree $n-1$ means that a vertex is connected to every other n-1 vertices.

Both statements cannot be true simultaneously.

This means that our assumption is Wrong and such a graph cannot exist. 

edited by
5 votes
5 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

Related questions

15 votes
15 votes
3 answers
1
makhdoom ghaya asked Nov 14, 2016
1,794 views
Show that the number of odd-degree vertices in a finite graph is even.
19 votes
19 votes
3 answers
2
Kathleen asked Oct 8, 2014
5,678 views
Prove that in finite graph, the number of vertices of odd degree is always even.
21 votes
21 votes
5 answers
3
Arjun asked Nov 15, 2015
5,718 views
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
2 votes
2 votes
0 answers
4