
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
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 . Since E = V  1, we have . 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, .
But then which is impossible?

Re: proof with graphs