Use the handshake lemma 4.1.5. What would happen if all the vertices had degree 2?