Michael Sipser Edition 3 Exercise 0 Question 13 (Page No. 27)

Question

Show that every graph with two or more nodes contains two nodes that have equal degrees.

Answer 1

The possible degrees for a graph with $n$ vertices is either $0,1,2, \dots, n-2$ or $1,2,3,\dots,n-1$.

Each of these contain $n-1$ degrees which have to be assigned to $n$ nodes.

Thus, by pigoenhole principle, there have to be at least two vertices of the same degree.