In any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree?
This one is a bit tricky! Here is the idea. We would like to use the pigeonhole principle. However, there are $n$ vertices and $n$ possible degrees $0,\ldots,n-1$, so the pigeonhole principle allows the situation in which each degree appears exactly once. We can flatly rule it out for values of $n$ which are of the form $4m+2$ or $4m+3$ using the handshake lemma, which states that the sum of the degrees is even, but what about the general case?

It turns out that to solve the general case we don't even need the handshake lemma. The following observation suffices (and explains why we need $n&gt;1$):


   If $n &gt; 1$ then a graph cannot contain both a node of degree $0$ and a node of degree $n-1$.