# proof with graphs

• Jun 4th 2013, 11:21 PM
Yuuki
proof with graphs
The graph G contains at least two vertices. One vertex has degree one, and every other vertex has degree greater than 1. Show that G contains a cycle.

I was able to see that it was the case by drawing, but I need help getting started with the proof.
I tried to make a connection with the theorem that says any walk starting with an odd degree must end in another odd degree vertex, but failed.
• Jun 7th 2013, 04:15 AM
emakarov
Re: proof with graphs
If G does not have a cycle, then it is a tree, and in a tree, |V| = |E| + 1 where V is the set of vertices and E is the set of edges. Used together with the handshaking lemma and with the assumption about the degrees, this leads to a contradiction.
• Jun 7th 2013, 10:39 AM
Yuuki
Re: proof with graphs
So $|V|=|E|+1 \\ \Rightarrow 2|E|=|E|+1 \\ \Rightarrow |E|=1$
and this is a contradiction because we assumed G has more than two vertices?
• Jun 7th 2013, 10:53 AM
emakarov
Re: proof with graphs
No, it does not follow from anywhere that 2|E| = |V| (this fact, I assume, is used in going from the first to the second line). Rather, the handshaking lemma says that $\sum_{v\in V} \mathop{\text{deg}}(v)=2|E|$. Since |E| = |V| - 1, we have $\sum_{v\in V} \mathop{\text{deg}}(v) =2(|V|-1)$. Now find a lower bound for the left-hand side and compare it with the right-hand side.
• Jun 7th 2013, 12:37 PM
Yuuki
Re: proof with graphs
From the assumption about the degrees, $\sum_{v\in V} \mathop{\text{deg}}(v) \ge 1+2(|V|-1)$.
But then $\sum_{v\in V} \mathop{\text{deg}}(v) =2(|V|-1) \ge 1+2(|V|-1)$ which is impossible?
• Jun 8th 2013, 12:25 AM
emakarov
Re: proof with graphs
That's correct.