Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
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. –  Erick Wong Dec 6 '12 at 17:43
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$. –  Thomas Andrews Dec 6 '12 at 17:51

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
@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
    
Yeah, I was misreading the words "loop-free" as "cycle-free." Never mind. –  Thomas Andrews Dec 6 '12 at 18:14
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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