What is the Handshake Lemma?

The Handshake Lemma (also called the Handshaking Lemma) states that the sum of the degrees of all vertices in a graph equals twice the number of edges. In symbols:

∑ deg(v) = 2 × |E|

Why is this true? Every edge connects two vertices, so it contributes 1 to the degree of each of the two vertices it connects. Therefore, every edge adds 2 to the total degree sum. It's like counting handshakes at a party — each handshake involves two people, so the total number of handshakes is half the sum of everyone's handshake count.

In our puzzle, you're given a degree sequence (the degree of each vertex). You compute total edges, take that number mod 26, and map to a letter of the alphabet.

A Concrete Example

Let's work through a complete example.

Setup

We have 4 vertices with degrees [3, 2, 2, 1].

Imagine a graph with 4 vertices. Vertex A is connected to 3 others, vertices B and C are connected to 2 others each, and vertex D is connected to just 1 other vertex.

Step 1: Sum the degrees

sum = 3 + 2 + 2 + 1 = 8

Step 2: Divide by 2 to get edges

edges = 8 / 2 = 4

Step 3: Map to a letter

4 % 26 = 4 → 'e' (a=0, b=1, c=2, d=3, e=4)

The answer letter is 'e'.

Verification

Let's verify: 4 edges in a graph with degree sequence [3, 2, 2, 1]. A graph with degrees 3, 2, 2, 1 could be a chain of 4 vertices where the first vertex connects to all three others, the last vertex connects only to the first, and the middle two connect to the first and each other. That's exactly 4 edges.

Why It Works: Graph Theory in One Paragraph

Every edge has two endpoints. The degree of a vertex counts how many edges touch it. When you sum all degrees, each edge is counted exactly twice — once at each endpoint. This means the sum of degrees is always an even number, and half of it is the number of edges. This simple observation is the foundation of countless graph theory results, including Euler's famous solution to the Königsberg bridge problem.

Solving Tips

• Add up all the numbers in the degree sequence
• Divide by 2 — this gives you the number of edges (handshakes)
• Take edges mod 26 to get a number from 0 to 25
• Convert to a letter: a=0, b=1, ..., z=25
• The sum of degrees is always even (the Handshake Lemma guarantees it)

Difficulty Table

Real-World Applications

• Network Analysis: The Handshake Lemma is used to verify the consistency of network data. If someone reports a degree sequence with an odd sum, you know there's an error.
• Social Networks: The "handshake" metaphor is literal — at a conference with known attendee connections, you can verify the total number of handshakes.
• Computer Networks: Router connections in a network form a graph. The lemma helps network engineers verify port counts and connection data.
• Biology: Protein-protein interaction networks use the lemma to check consistency of experimental data.
• Chemistry: Molecular graphs where vertices are atoms and edges are bonds — the degree sum is twice the bond count.

Want to Try It?

Head over to the active puzzles page.