Exercise 240Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

The handshake lemma

#handshake lemma#degree sum#parity

Statement

Prove that in any graph $\sum_{v\in V}\deg(v)=2|E|$ . Deduce that the number of odd-degree vertices is even.

Hint

Double count the set of incidences $(v,e)$ where $v$ is an endpoint of $e$ .

Show solutionHide solution

Solution

Double count. Count incidences $\{(v,e):v\in e\}$ .

By vertex. $\sum_v\deg(v)$ .

By edge. Each edge has $2$ endpoints: $2|E|$ .

Conclusion. $\sum_v\deg(v)=2|E|$ , hence even. Splitting degrees into even and odd parts: the odd-degree sum must be even, so there are an even number of odd-degree vertices.

The handshake lemma

Statement

Solution

More problems in Graph theory