# Pigeonhole Principle on Graphs

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!

-
Doesn't look like a pigeonhole principal problem to me. – Thomas Andrews Dec 6 '12 at 17:36
Hm. Maybe I'm confusing it with another one. I just thought I remembered it being answered as a pigeonhole principle question. I'll try to tackle it differently – connorbode Dec 6 '12 at 17:38
has at leat 2 vertices or exactly two vertices ? – Amr Dec 6 '12 at 17:42
@somekindarukus This is a sort of converse to the well-known fact that in every simple graph there are two vertices with the same degree. This latter problem is a very standard application of pigeonhole. – Erick Wong Dec 6 '12 at 17:43
@Amr "Exactly" or "At least" are the same here. There are $2n$ nodes. If, for each $i$, there are at least two nodes with degree $i$, then, for each $i$, there are exactly two nodes with degree $i$. – Thomas Andrews Dec 6 '12 at 17:51

Suppose that you have a bipartite graph $G_n$ with vertex classes $V_0$ and $V_1$, each containing $n$ vertices, one of each degree from $1$ through $n$. Add an isolated vertex to each part to get a bipartite graph $H_n$, each of whose parts contains one vertex of degree $k$ for $k=0,\dots,n$. Now add one more vertex to each part, connecting it by an edge to each vertex in the other part. The resulting graph $G_{n+2}$ will be bipartite, and each part will contain one vertex of degree $k$ for $k=1,\dots,n+2$.
@Thomas: That’s easy: just do it. Take vertices $1,2,3,1',2',3'$ with edges $\{3,1'\},\{3,2'\},\{3,3'\}$, $\{2,3'\},\{2,2'\}$, and $\{1,3'\}$. – Brian M. Scott Dec 6 '12 at 18:10
I just want to note that the graphs need not necessarily be bipartite. You can do a one step induction from $n$ to $n+1$. If $G_n$ is divided into two vertex classes, $V_0$ and $V_1$, of size $n$, each containing one vertex of degree $k$ for $1\leq k \leq n$, then we simply add two isolated vertices, $v_0$ and $v_1$, and add edges from $v_i$ to the $\lfloor \frac{n+1}{2} \rfloor$ vertices of largest degree in $V_i$, $i=1,2$. Then, if $n$ is even, add the edge ${v_0,v_1}$. Note that for $n \geq 4$, $G_n$ is NOT bipartite. – Kevin Halasz Jan 18 '13 at 22:53