Bonus question A graph is called simple if it has no loops o

Bonus question: A graph is called simple if it has no loops or multi-edges. Does a simple graph exist with all vertices having different degrees? Hint: Google then use “pigeonhole principle”.

Solution

A graph is called simple if it has no loops or multi-edges. Does a simple graph exist with all vertices having different degrees ?

Answer :-

No

Explanation :-

If a simple graph with 8 vertices, whose degrees are 0, 1, 2, 3, 4, 5, 6, 7. which satisfies the Handshaking Theorem i.e the sum of the degrees is even. The problem lies in the fact that one of the vertices has seven incident edges, and therefore, there must be seven incident vertices, but in this graph, although there are seven other vertices, one of them is reported as having no incident edges. Since a simple graph cannot have loops or multiple edges, it is impossible to have a vertex in this graph which connects to seven vertices when one of the only other seven vertices is not accepting an edge which means that this graph cannot exist.