GATE CSE 1991 | Question: 16-b

Question

Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.

Comments

GATE CSE 2009 | Question: 3 - GATE Overflow for GATE CSE

---

🕊🕳

---

If it would have been infinite graph then its possible right because at infinity we cannot say about the degree of the vertex so we consider it undefined ?

A(deg=0)----------------------------------------at infinity let there exist B(deg=undefined)

Answer 1

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

Comments

@rajankakaniya You are correct. A finite graph doesn't mean a simple graph because you can draw a multigraph that is finite. 

---

What is an infinte graph then?

---

A graph that has either an infinite number of edges or vertices or both.

Answer 2

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. 

Comments

nope @prithatiti if self loops and multiedges are allow then u can make a  graph for which each vertex can have diff degree  assume 2 vertex a,b now a,b are connected with multiedge and now u can make one of degree diff by appending a self loop .

---

this should be the best answer

---

yeah nice explaination

Answer 3

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