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?

Solution 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.

Solution 2:

I will show only the case where no vertex has an edge going to itself. Assume a graph with $n$ vertices does not have at least two vertices of the same degree. Then one vertex has degree one, second vertex has degree two,..., $nth$ vertex has degree $n$, for some ordering of the vertices. Then the $nth$ vertex must be connected to $n$ other vertices. But then there are $n+1$ vertices, so that we have a contradiction.