Handshaking Lemma

Exercises 5.5 and 5.6

Exercise 5.5

Prove the Handshaking Lemma, that is prove that in every undirected graph G = (V, E) we have

\sum_{u\in V}\mathrm{deg}(u)=2|E|\ ,

where \mathrm{deg}(u)=|\{v\in V : \{u,v\}\in E\}|.

Exercise 5.6

Consider an undirected graph with 5 vertices, all of them with degree 3. If such a graph exists, draw it. If it doesn’t, give a reasoned explanation.