
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.

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.

Re: proof with graphs
So $\displaystyle V=E+1 \\ \Rightarrow 2E=E+1 \\ \Rightarrow E=1$
and this is a contradiction because we assumed G has more than two vertices?

Re: proof with graphs
No, it does not follow from anywhere that 2E = V (this fact, I assume, is used in going from the first to the second line). Rather, the handshaking lemma says that $\displaystyle \sum_{v\in V} \mathop{\text{deg}}(v)=2E$. Since E = V  1, we have $\displaystyle \sum_{v\in V} \mathop{\text{deg}}(v) =2(V1)$. Now find a lower bound for the lefthand side and compare it with the righthand side.

Re: proof with graphs
From the assumption about the degrees, $\displaystyle \sum_{v\in V} \mathop{\text{deg}}(v) \ge 1+2(V1)$.
But then $\displaystyle \sum_{v\in V} \mathop{\text{deg}}(v) =2(V1) \ge 1+2(V1)$ which is impossible?

Re: proof with graphs