Lesson 3

What we've just proved is known as the handshaking lemma:

Before a business meeting, some people shook hands. Then, the number of people who made an odd number of handshakes is even.

In graph terms, it is stated as follows.

Lemma (handshaking lemma).A graph has an even number of nodes of odd degree.

In turn, the handshaking lemma follows from the following formula.

Lemma (degree sum formula).For any graph \(G(V,E)\), the sum of degrees of all its nodes is twice the number of edges: \[\sum_{v \in V}\deg(v) = 2 \cdot |E| \ .\]

Proof. In short, each edge contributes 2 to the sum of degrees as well as to twice the number of edges.

For a more formal proof, one can proceed by induction on \(|E|\).

• Base case:  \(|E|=0\). Then, there are no edges in the graph and the sum of degrees is just zero.


• Induction step.  Remove an edge \(\{u,v\} \in E\) from the graph. The resulting graph has \(|E|-1\) edges, hence, by the induction hypothesis, the sum of degrees is equal to \(2(|E|-1)\). Now, restore the edge \(\{u,v\}\). This increases the total degree by two as both the degree of \(u\) and the degree of \(v\) are incremented by one. Hence, the total degree is \[2(|E|-1)+2=2|E|.\]

◼

This is how this formula implies the handshaking lemma: if a graph has an odd number of nodes of odd degree, then the sum of the degrees is odd, but it cannot be odd as it is equal to twice the number of edges.