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
    Doesn't look like a pigeonhole principal problem to me.2012-12-06
  • 0
    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 differently2012-12-06
  • 0
    has at leat 2 vertices or exactly two vertices ?2012-12-06
  • 0
    it looks like a mathematical induction problem to me2012-12-06
  • 0
    doesn't specify exactly or at least2012-12-06
  • 1
    @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.2012-12-06
  • 0
    @BrianM.Scott That doesn't seem to work, since every old node gets its degree incremented and the nodes will not be of degree $1$, so you are left with no nodes of degree 1.2012-12-06
  • 0
    @Thomas: Not quite, no; I need to play with it a little more.2012-12-06
  • 1
    @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$.2012-12-06
  • 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
    @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'\}$.2012-12-06
  • 0
    Yeah, I was misreading the words "loop-free" as "cycle-free." Never mind.2012-12-06
  • 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