IB Maths AI HL Graph Theory Paper 1 & 2 Hamiltonian cycles ~7 min read

Travelling Salesman Problem

The Travelling Salesman Problem (TSP) asks: what’s the shortest closed route that visits every vertex exactly once? This closed route is a Hamiltonian cycle. For the classical TSP (graph complete and direct route is shortest), the only general method is brute force — list every Hamiltonian cycle, compute its weight, pick the smallest.

📘 What you need to know

Hamiltonian path: visits every vertex exactly once.
Hamiltonian cycle: a Hamiltonian path that returns to the starting vertex (only the start vertex is repeated).
Hamiltonian graph: contains a Hamiltonian cycle. Semi-Hamiltonian: contains a Hamiltonian path but no cycle.
No degree test: unlike Eulerian, there is no easy degree-based check. The only way to prove a graph is Hamiltonian is to find a Hamiltonian cycle.
Classical TSP conditions: (i) graph is complete, (ii) direct edge between any two vertices is the shortest route (triangle inequality).
TSP method: list all Hamiltonian cycles, sum the edge weights of each, pick the minimum.
Number of cycles: for n vertices there are (n − 1)! cycles to consider. Each pair (a cycle and its reverse) has equal weight, so only (n − 1)! / 2 distinct totals.
Brute force is only practical for small graphs (typically up to 5 vertices). Larger graphs need the bounds covered on the next page.
Postman vs Salesman: postman walks every edge at least once; salesman visits every vertex exactly once.

Hamiltonian paths and cycles

A Hamiltonian path visits every vertex once; a Hamiltonian cycle does the same and returns to the start. There is no quick formula to decide whether a Hamiltonian cycle exists in a graph — the only way is to find one. This is the key difference from Eulerian, where counting odd-degree vertices gives an instant answer.

Postman vs Salesman: the postman walks every edge at least once (Eulerian); the salesman visits every vertex exactly once (Hamiltonian). Postman = edges, salesman = vertices.

The classical TSP

The classical TSP assumes the graph is complete (every pair of vertices joined) and satisfies the triangle inequality (a direct edge is always at least as short as any indirect route). Under these conditions:

Classical TSP solution shortest closed route = min weight over all Hamiltonian cycles enumerate all (n − 1)! cycles, compute weights, take minimum

K₄ with edge weights AB=8, AC=12, AD=6, BC=10, BD=14, CD=7. All 3 distinct Hamiltonian cycles are listed on the right; the cheapest is A → B → C → D → A with weight 31.

How many cycles to check?

Vertices n	Cycles to list = (n−1)!	Distinct totals = (n−1)! / 2
3	2	1
4	6	3
5	24	12
6	120	60
7	720	360

Brute force is fine up to 5 vertices. Beyond that, use the bounding methods (next page).

🧭 Recipe — solving classical TSP

Fix a starting vertex (any one works).
List all (n − 1)! orderings of the other vertices — each gives a Hamiltonian cycle.
Compute the weight of each cycle by summing its n edge weights.
Pair up reverses (same weight) to halve the work.
Pick the minimum. State the route and its weight.

Worked examples

WE 1

Find a Hamiltonian cycle

A graph G has vertices { A, B, C, D, E } and edges AB, AE, BC, BD, CD, CE, DE. Show that G is Hamiltonian by finding a Hamiltonian cycle.

try a cycle that uses available edges A → B → C → E → D → ? need edge back to A DA not in edge list → try another order try A → B → D → C → E → A edges used: AB ✓, BD ✓, DC ✓, CE ✓, EA ✓ Hamiltonian cycle: A → B → D → C → E → A a Hamiltonian cycle is found ⇒ G is Hamiltonian.

WE 2

Hamiltonian vs Eulerian

The complete graph K₄ has 4 vertices each of degree 3. Is K₄ Eulerian? Is it Hamiltonian?

Eulerian check (degrees) every vertex has degree 3 (odd) 4 odd vertices → not Eulerian Hamiltonian check (find a cycle) try A → B → C → D → A: all edges exist in K₄ K₄: not Eulerian, but Hamiltonian degrees decide Eulerian; only finding a cycle decides Hamiltonian.

WE 3

Classical TSP on 4 vertices

A complete graph has vertices { A, B, C, D } with edge weights AB(6), AC(4), AD(7), BC(8), BD(3), CD(5). Find the shortest Hamiltonian cycle and state its weight.

list all (4−1)! = 6 cycles from A ABCDA = 6 + 8 + 5 + 7 = 26 ABDCA = 6 + 3 + 5 + 4 = 18 ★ ACBDA = 4 + 8 + 3 + 7 = 22 ACDBA = 4 + 5 + 3 + 6 = 18 (reverse of ABDCA) ADBCA = 7 + 3 + 8 + 4 = 22 (reverse of ACBDA) ADCBA = 7 + 5 + 8 + 6 = 26 (reverse of ABCDA) minimum weight min = 18 shortest route: ABDCA (or ACDBA); weight = 18 3 distinct totals: 18, 22, 26 — each appears twice (forward and reverse).

WE 4

Classical TSP — distinct cycles only

A complete graph has vertices { A, B, C, D } with weights AB(12), AC(8), AD(20), BC(10), BD(15), CD(5). Find the minimum Hamiltonian cycle weight by considering only the 3 distinct cycles.

list 3 distinct cycles ABCDA = 12 + 10 + 5 + 20 = 47 ABDCA = 12 + 15 + 5 + 8 = 40 ★ ACBDA = 8 + 10 + 15 + 20 = 53 minimum shortest route: ABDCA (or its reverse ACDBA); weight = 40 listing 3 distinct cycles is enough — each represents a pair of reverse routes with the same weight.

WE 5

Delivery driver — 4 cities

A driver based in city W must deliver to cities X, Y, Z and return to W. Distances (in km): WX(20), WY(35), WZ(18), XY(22), XZ(30), YZ(14). Find the shortest delivery route.

list 3 distinct cycles starting at W WXYZW = 20 + 22 + 14 + 18 = 74 ★ WXZYW = 20 + 30 + 14 + 35 = 99 WYXZW = 35 + 22 + 30 + 18 = 105 minimum shortest route: W → X → Y → Z → W; distance = 74 km reverse W → Z → Y → X → W has the same total — also valid.

WE 6

Number of cycles for larger graphs

A complete graph has 7 vertices. How many Hamiltonian cycles must be checked by brute force? How many distinct totals? Why is brute force impractical here?

number of cycles = (n − 1)! = (7 − 1)! = 6! = 720 distinct totals = (n − 1)! / 2 = 720 / 2 = 360 720 cycles to check; 360 distinct totals at 360 sums by hand, brute force is impractical. Use bounding methods (next page) instead.

💡 Top tips

Fix the start: choose any vertex as the start; all cycles must come back to it.
Halve the work using reverses: each cycle and its reverse give the same total — only list (n − 1)! / 2 distinct cycles.
Show every cycle and weight: examiners want all sums, not just the minimum — method marks.
Brute force only up to 5 vertices: 24 cycles is the practical limit. For 6+ use bounds.
No degree test for Hamiltonian: you must find a Hamiltonian cycle to prove existence.

⚠ Common mistakes

Confusing postman with salesman: postman = every edge; salesman = every vertex.
Trying a degree-based test for Hamiltonian: degrees don’t help. Find the cycle directly.
Missing one of the cycles: when listing by hand, double-check you have all (n − 1)! permutations.
Adding edges instead of cycle weights: each cycle uses exactly n edges; double-check the sum.
Forgetting the return edge: a Hamiltonian cycle on 4 vertices uses 4 edges, not 3 — the last edge back to the start counts.

Next up — Nearest Neighbour & Deleted Vertex Algorithms. For graphs with 6 or more vertices, listing all (n − 1)! cycles is impractical. Instead, sandwich the true minimum between an upper bound (nearest neighbour algorithm) and a lower bound (deleted vertex algorithm).

Need help with Graph Theory?

Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.

Book Free Session →