The Handshake Lemma

Counting degrees

An interactive lesson with 7 steps, about 6 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• The sum of the degrees = 2 × the number of edges.
• Every graph has an even number of odd-degree vertices.
• Counting the same thing two ways is a powerful proof technique.

Steps

1. Total degree
2. The handshake lemma
3. Possible party?
4. Everybody shakes hands
5. Same number of friends
6. Count the odd ones
7. How many edges?