Handshaking Lemma — Definition, Formula & Example
The Handshaking Lemma is the fact that if you add up the degrees of all the vertices in an undirected graph, you get exactly twice the number of edges. The name comes from a party: if you add up how many hands each guest shook, every handshake is counted twice.
Let be a finite undirected graph. Multiple edges are allowed, and a loop contributes 2 to the degree of its vertex. Then . Corollary: every finite undirected graph has an even number of vertices of odd degree.
Key Formula
Where:
- = The set of vertices of the graph
- = The degree of vertex v, which is the number of edge endpoints at v (a loop counts 2)
- = The number of edges in the graph
How It Works
The proof uses double counting. Count the pairs (v, e) where vertex v is an endpoint of edge e. Counting by vertices, vertex v appears in exactly deg(v) pairs, so the total is the sum of the degrees. Counting by edges, each edge has exactly two endpoints (a loop counts its vertex twice), so the total is 2|E|. Both counts describe the same set, so they are equal. For the corollary, the even-degree vertices contribute an even amount to the sum. The odd-degree vertices must then also sum to an even number, and that can only happen if there is an even number of them.
Worked Example
Problem: A graph has 15 edges. Four of its vertices have degree 5, and every other vertex has degree 2. How many vertices does the graph have?
Step 1: Apply the Handshaking Lemma to find the total degree.
Step 2: The four degree-5 vertices contribute 20 of that total. Let k be the number of degree-2 vertices, which together contribute 2k.
Step 3: Add the two groups of vertices.
Answer: The graph has 9 vertices: 4 of degree 5 and 5 of degree 2.
Why It Matters
In a discrete math or graph theory course, the lemma is often the quickest way to show that a graph cannot exist. For example, no group of 7 people can each be friends with exactly 3 others, because is odd. It also gives edge counts directly, such as for an r-regular graph on n vertices. In addition, it supports results about Euler paths, where the number of odd-degree vertices is what matters.
Common Mistakes
Mistake: Concluding that a list of degrees forms a simple graph just because the degrees add up to an even number.
Correction: An even sum is necessary but not sufficient. The sequence 3, 3, 1, 1 sums to 8, but no simple graph has these degrees. Each degree-3 vertex would have to be adjacent to all three other vertices, which forces the last two vertices to have degree at least 2. To test a degree sequence for a simple graph, use the Havel–Hakimi algorithm or the Erdős–Gallai theorem.
