1. ## 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.

2. ## 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.

3. ## 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?

4. ## 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.

5. ## 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?

6. ## Re: proof with graphs

That's correct.