2
$\begingroup$

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!

  • 0
    Oh, I'm misunderstanding the term "loop-free." Was reading that as "cycle-free." Never mind.2012-12-06

1 Answers 1

5

You can do it by induction, but the induction skips a size, so you’ll need to check two consecutive base cases.

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$.

  • 0
    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.2013-01-18