I just have a last minute question for my combinatorics final (which is in one hour!!).
My prof particularly told me to study the following question and I'm pretty sure it involves the pigeonhole principle but I can't remember how it applies. Can anyone help me out?
Prove that for each $n \in \mathbb{Z}^+$ There exists a loop-free connected undirected graph $G=(V,E)$, where $|V|=2n$ and which has two vertices of degree $i$ for every $1 \leq i \leq n$.
Any help is greatly, greatly appreciated!