Snazzy application of pigeonhole principle.

Problem: Prove that a simple graph $G$ with $n > 2$ vertices has at least two vertices with the same degree.

Solution: Notice that there is no guarantee that $G$ is connected. However let us suppose that it is. Then each vertex has degree $d$ where $d \in \{1, 2, ..., n - 1\}$. Since we have $n$ vertices and $n - 1$ degree choices, it must be that at least two vertices in $G$ have the same degree.

This proves the case when $G$ is connected, but what about when it is unconnected?

In this case, each vertex can connect to at most $n - 2$ vertices because for $G$ to be unconnected, there must exist a vertex which is connected to no other vertex. Therefore, each vertex has degree $d$ where $d \in \{0, 1, ..., n - 2\}$. By the same argument used in the connected case, $G$ must have at least two vertices of the same degree.

I thought this was a pretty snazzy approach. There is something so elegant about the pigeonhole principle.