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