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.
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.
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.
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 . Since |E| = |V| - 1, we have . Now find a lower bound for the left-hand side and compare it with the right-hand side.