The Handshaking Lemma and Graph Traversability
One elementary fact about graphs — that the sum of all vertex degrees equals twice the number of edges — has an immediate and powerful consequence: you can tell, just by counting degrees, whether a graph can be traversed in a single journey without repeating an edge, and whether that journey must return to where it started.
The handshaking lemma
In any graph, each edge contributes exactly 1 to the degree of each of its two endpoints — so it contributes 2 to the total degree count across all vertices:
Since the right-hand side is always even, the sum of all degrees is always even. This forces an immediate consequence:
The number of odd-degree vertices in any graph is always even.
Why “handshaking”?
Imagine n people at a party, each shaking hands with some others. The degree of each person is how many hands they have shaken. Each handshake involves exactly two people, so it adds 1 to each of their degree counts — contributing 2 to the total. The total number of handshakes is therefore always half the total degree count, and is always a whole number.
A quick sanity check: it is impossible for an odd number of people to each shake hands an odd number of times. If that seems surprising, the lemma makes it obvious — odd × odd = odd, and summing an odd number of odd values gives an odd total, contradicting the requirement that the sum be even.
Traversability: crossing every edge exactly once
A classic puzzle — can you draw a shape without lifting your pen and without retracing any line? In graph theory, this is the question of whether a graph has an Eulerian trail: a route that crosses every edge exactly once.
The answer comes directly from the handshaking lemma. Think about what happens at each vertex as you traverse the graph:
- At any intermediate vertex (one you pass through without starting or finishing), you arrive along one edge and leave along another. Each pass through the vertex uses 2 edges. For all edges at that vertex to be used, it must have even degree.
- At the start vertex (if different from the end), you leave first, then possibly arrive and leave again, and finally leave for the last time — so you leave one more time than you arrive. The vertex must have odd degree.
- Similarly, the end vertex (if different from the start) must have odd degree.
The handshaking lemma guarantees there are always an even number of odd-degree vertices — so there can never be, say, exactly one or three odd-degree vertices. The only possibilities are 0, 2, 4, … odd-degree vertices.
The three cases
No odd-degree vertices — Eulerian graph
If every vertex has even degree, the graph is Eulerian: it has a closed Eulerian trail (an Eulerian circuit) — a route that traverses every edge exactly once and returns to the starting vertex. You can begin anywhere and the journey will close.
Exactly two odd-degree vertices — semi-Eulerian graph
If exactly two vertices have odd degree, the graph is semi-Eulerian: it has an open Eulerian trail — a route that traverses every edge exactly once but does not return to the start. The trail must begin at one of the two odd-degree vertices and end at the other. There is no choice about this: any Eulerian trail must start and finish at the odd-degree vertices.
Four or more odd-degree vertices — not traversable in one journey
If there are four or more odd-degree vertices, no Eulerian trail exists. The graph cannot be traversed in a single journey without repeating at least one edge. This is the situation addressed by the Route Inspection (Chinese Postman) problem: find the minimum number of edges that must be repeated to make the graph traversable.
To do this, pair up the odd-degree vertices and find the pairing that minimises the total weight of the shortest paths between paired vertices. Adding those paths (repeating their edges) reduces the number of odd-degree vertices to zero, making the augmented graph Eulerian.
| Odd-degree vertices | Type | Trail exists? | Start and end |
|---|---|---|---|
| 0 | Eulerian | Yes — closed circuit | Any vertex; returns to start |
| 2 | Semi-Eulerian | Yes — open trail | Must start and end at the two odd vertices |
| 4, 6, 8, … | Neither | No | Some edges must be repeated |
| 1, 3, 5, … (odd count) | Impossible | — | Cannot occur — handshaking lemma |
Worked example
A graph has six vertices A, B, C, D, E, F with the following edges: AB, AC, BC, BD, CD, CE, DE, DF, EF. Determine whether the graph is Eulerian, semi-Eulerian, or neither.
Step 1 — find the degree of each vertex
| Vertex | Edges incident | Degree | Odd or even? |
|---|---|---|---|
| A | AB, AC | 2 | Even |
| B | AB, BC, BD | 3 | Odd |
| C | AC, BC, CD, CE | 4 | Even |
| D | BD, CD, DE, DF | 4 | Even |
| E | CE, DE, EF | 3 | Odd |
| F | DF, EF | 2 | Even |
Step 2 — check the handshaking lemma
Step 3 — count odd-degree vertices and conclude
Vertices B and E have odd degree. There are exactly two odd-degree vertices, so the graph is semi-Eulerian. An Eulerian trail exists, and it must start at B and end at E (or vice versa).
A common confusion: Eulerian vs Hamiltonian
Eulerian trails are sometimes confused with Hamiltonian paths, which are a completely different concept. The distinction is worth making explicit:
| Eulerian trail | Hamiltonian path | |
|---|---|---|
| Visits | Every edge exactly once | Every vertex exactly once |
| Vertices/edges | Vertices may be revisited | Edges may be skipped |
| Test | Count odd-degree vertices (0 or 2) | No simple degree-based test exists |
| Application | Route inspection, network traversal | Travelling salesman problem |
The handshaking lemma gives a clean, complete answer for Eulerian traversal. For Hamiltonian paths, no such simple criterion exists — determining whether a graph has a Hamiltonian path is, in general, computationally hard (it is an NP-complete problem). The two concepts sound similar but are mathematically very different in character.