0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

Good luck!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Kuifje Feb 2 '16 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.