# Prove that every graph has two vertices that are endpoints of the same number of edges

Prove that every graph has two vertices that are endpoints of the same number of edges.

My proof was that in any graph with $n$ vertices, each vertex $v$ has have $1 \leq \deg(v) \leq n-1$. By a simple argument with pigeonhole it is seen that since there are $n$ vertices at least $2$ of them must have the same degree.

This proof seemed to easy to me, so I wanted to know if I made a mistake.

That is the main idea of the proof. However, in principle, the $n$ degrees could be $0,1,2,\ldots,n-1$, which are all different. If you can explain why this case is impossible, you will have completed the proof.
• Hint: assume the contrary, i.e. let $G$ be a graph where all vertices have different degrees. Can you see why this leeds to something wrong? – Kuifje Feb 2 '16 at 15:29