[Math] If $n$ is a natural number $\ge 2$ how to prove that any graph with $n$ vertices has at least two vertices of the same degree

Question

Any help would be appreciated.

If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?

Answer 1

HINT: The possible degrees of a simple graph with $n$ vertices are the $n$ integers $0,1,\dots,n-1$. However, a simple graph on $n$ vertices cannot have both a vertex of degree $0$ and a vertex of degree $n-1$; why?

That means that either the degrees of the $n$ vertices are all in the set $\{0,1,\dots,n-2\}$, or they’re all in the set $\{1,2,\dots,n-1\}$. How many numbers are in each of those sets? (In case that’s not enough of a hint, I’ve added a spoiler-protected further hint; mouse-over to see it.)

Pigeonhole principle.