Exercise 881Combinatorics › Counting principlesL1Added 3 Nov 2026
Handshake lemma
#double counting#graph#degree sum
Statement
In a party, some pairs of people shake hands. Show that the number of people who shook an odd number of hands is even.
Hint
Double count the number of handshakes: each edge counted twice.
Show solutionHide solution
Solution
Graph model. People are vertices, handshakes are edges. The sum of degrees equals .
Parity. degrees is even. Split into even-degree and odd-degree vertices: even-degree sum is even, so odd-degree sum is even. Since each odd degree is odd, there must be an even number of odd-degree vertices.
Conclusion. The number of people with odd degree is even.