IB Maths AI HL Graph Theory Paper 1 & 2 ~9 min read

Nearest Neighbour & Deleted Vertex Algorithms

When a TSP graph has 6 or more vertices, brute force becomes impractical — there are too many Hamiltonian cycles to list. The solution is to sandwich the unknown minimum between two bounds. The Nearest Neighbour algorithm (NN) finds a valid Hamiltonian cycle quickly, giving an upper bound. The Deleted Vertex algorithm (DV) finds a value the TSP minimum cannot drop below, giving a lower bound. If the two bounds happen to match, you’ve found the exact TSP minimum. Both methods need a complete graph satisfying the triangle inequality — so practical TSP problems must first be converted into a table of least distances.

📘 What you need to know

Practical TSP: a real-world TSP graph that may not be complete, or where the direct edge between two vertices isn’t always the shortest route. Must be converted to classical TSP form first.
Table of least distances: a complete weighted table where each cell holds the shortest route (not just the direct edge) between every pair of vertices. Always satisfies the triangle inequality.
Nearest Neighbour Algorithm (NN) — produces an upper bound for the TSP minimum. Start at any vertex, always move to the cheapest unvisited neighbour, then return to the start at the end.
Deleted Vertex Algorithm (DV) — produces a lower bound. Delete one vertex with all its edges, find the MST of what remains, then add the two shortest edges from the deleted vertex.
Best upper bound = lowest. Different starting vertices give different NN totals; the smallest is the tightest UB.
Best lower bound = highest. Different deleted vertices give different LB totals; the largest is the tightest LB.
Sandwich: best LB ≤ TSP minimum ≤ best UB. If LB = UB, that common value is the exact minimum.

Table of least distances

If a direct edge AC has weight 15 but A→B→C has weight 13, the shortest route from A to C is 13. The table of least distances replaces every direct edge weight with the shortest-route weight for every pair of vertices. This guarantees the resulting “graph” is complete and satisfies the triangle inequality — ready for NN and DV.

from practical graph to table of least distances

The direct edge AC = 15 isn’t the shortest A–C route — A→B→C = 13 is shorter, so the table records 13. The table is symmetric and always satisfies the triangle inequality.

Nearest Neighbour Algorithm — upper bound

The NN algorithm finds a valid Hamiltonian cycle quickly — just not necessarily the shortest one. Its weight is therefore an upper bound for the true TSP minimum.

Nearest Neighbour produces an upper bound TSP minimum ≤ weight of NN route try different starting vertices; the lowest NN total = best (tightest) upper bound

🧭 Recipe — Nearest Neighbour

Choose a starting vertex. Mark it visited.
From the current vertex, go to the nearest unvisited vertex (the smallest weight in its row, ignoring visited columns).
Repeat until every vertex has been visited.
Add the final edge from the last vertex back to the starting vertex.
Total weight = sum of all edges used. This is the upper bound for that starting vertex.

Deleted Vertex Algorithm — lower bound

The DV algorithm produces a value the TSP minimum cannot drop below. The idea: any Hamiltonian cycle, when you delete one vertex, leaves a connected path through the others (which must cost at least their MST), plus exactly two edges back to the deleted vertex.

Deleted Vertex produces a lower bound TSP minimum ≥ weight(MST of G − v) + (two shortest edges from v) try different deleted vertices; the highest LB = best (tightest) lower bound

🧭 Recipe — Deleted Vertex

Choose a vertex v to delete; remove it and all edges connected to it.
Find the MST of the remaining graph (Kruskal’s or Prim’s).
Identify the two shortest edges that were originally connected to v in the full graph.
Lower bound = MST weight + sum of the two shortest v-edges.

🤔 Why two edges from the deleted vertex?

A Hamiltonian cycle visits every vertex exactly once, so it enters and leaves the deleted vertex using exactly two edges. The cheapest possible pair is the two shortest edges from v. The rest of the cycle connects all remaining vertices in a tree-like fashion, costing at least the MST weight.

Sandwich the answer

Nearest Neighbour

UPPER bound

A real route → TSP min ≤ this. Try several starts; pick the lowest.

Deleted Vertex

LOWER bound

TSP min ≥ this. Try deleting different vertices; pick the highest.

Bounding the TSP minimum best LB ≤ TSP minimum ≤ best UB if LB = UB, that common value is the exact TSP minimum

🧠 Memory aid — which bound goes which way

Upper bound: Use the route ⇒ NN gives a real cycle weight (achievable). Lower bound: a value the TSP can’t go below ⇒ DV. Lower bound’s best is the highest, upper bound’s best is the lowest — opposites!

Worked examples

WE 1

Construct a table of least distances

A graph has 4 vertices { A, B, C, D } and direct edges AB(8), AC(15), BC(5), BD(4), CD(6). There is no direct edge AD. Construct the table of least distances.

check each pair for shortest route AB: direct = 8 ✓ AC: direct=15 vs A→B→C = 8+5 = 13 ⇒ 13 AD: no direct edge via B: A→B→D = 8+4 = 12 via B,C: A→B→C→D = 19 ⇒ 12 BC = 5, BD = 4, CD = 6 (all direct ✓) table of least distances A row: −, 8, 13, 12 B row: 8, −, 5, 4 C row: 13, 5, −, 6 D row: 12, 4, 6, − complete table; satisfies triangle inequality always test non-direct paths — the direct edge isn’t always shortest.

WE 2

Nearest Neighbour starting at A

Using the table of least distances below, apply NN starting at A to find an upper bound for the TSP minimum.

	A	B	C	D	E
A	—	10	8	15	12
B	10	—	6	9	11
C	8	6	—	7	4
D	15	9	7	—	5
E	12	11	4	5	—

start at A; nearest unvisited row A: B=10, C=8, D=15, E=12 → go to C at C; ignore column A row C: B=6, D=7, E=4 → go to E at E; ignore A, C row E: B=11, D=5 → go to D at D; ignore A, C, E row D: B=9 → go to B at B; all visited → return to A B→A = 10 total 8 + 4 + 5 + 9 + 10 = 36 UB from A: route A→C→E→D→B→A, weight = 36 there must be exactly one selected weight in each column — verify before continuing.

WE 3

Compare upper bounds from different starts

Using the same 5-vertex table from WE 2, apply NN starting at B and at E. State the best (lowest) upper bound for the TSP minimum.

start B: nearest = C(6) B→C(6)→E(4)→D(5)→A(15)→B(10) total = 6+4+5+15+10 = 40 start E: nearest = C(4) E→C(4)→B(6)→D(9)→A(15)→E(12) total = 4+6+9+15+12 = 46 compare all three (WE 2 + WE 3) A: 36, B: 40, E: 46 best UB = 36 (starting at A) lowest UB is the tightest — always try multiple starts when asked for “the” UB.

WE 4

Deleted Vertex deleting A

Using the same table, find a lower bound by deleting vertex A and applying Kruskal’s algorithm to the remaining graph.

delete A; remaining edges BC=6, BD=9, BE=11, CD=7, CE=4, DE=5 Kruskal’s MST on 4 vertices sort: CE(4), DE(5), BC(6), CD(7), BD(9), BE(11) CE(4) → add ✓ DE(5) → add ✓ BC(6) → add ✓ (3 edges, n−1 reached) MST weight = 4+5+6 = 15 two shortest edges from A row A: 8, 10, 12, 15 → smallest two: 8, 10 lower bound LB = 15 + 8 + 10 = 33 LB deleting A = 33 do Kruskal’s first, then add the two smallest edges from the deleted vertex.

WE 5

Best lower bound — try different deletions

Find lower bounds by deleting C, and by deleting D. State which deletion gives the best (highest) lower bound.

delete C; remaining edges AB=10, AD=15, AE=12, BD=9, BE=11, DE=5 MST: sort 5, 9, 10, 11, 12, 15 DE(5)✓, BD(9)✓, AB(10)✓ → MST = 24 two shortest from C row C: 4, 6, 7, 8 → smallest two: 4, 6 LB deleting C = 24 + 4 + 6 = 34 delete D; remaining edges AB=10, AC=8, AE=12, BC=6, BE=11, CE=4 MST: sort 4, 6, 8, 10, 11, 12 CE(4)✓, BC(6)✓, AC(8)✓ → MST = 18 two shortest from D row D: 5, 7, 9, 15 → smallest two: 5, 7 LB deleting D = 18 + 5 + 7 = 30 compare with WE 4 A: 33, C: 34, D: 30 best LB = 34 (delete C) ★ highest LB is the tightest — always try several deletions.

WE 6

Sandwich the TSP minimum

Using all your results from WE 2–5, sandwich the TSP minimum between bounds. State an interval that must contain the exact minimum.

best UB from WE 2 & 3 UB = 36 (start at A) best LB from WE 4 & 5 LB = 34 (delete C) sandwich 34 ≤ TSP min ≤ 36 TSP minimum is in [34, 36] LB ≠ UB here, so we can’t pin down the exact value — but the interval is tight. If LB = UB, that’s the exact answer.

💡 Top tips

Practical TSP first → table of least distances. Always check whether direct edges are actually the shortest paths.
NN: best UB = lowest. DV: best LB = highest. Don’t mix these up.
For NN, the cheapest weight in each row (excluding visited columns) is your next move — keep tracking which columns have been visited.
Two shortest edges from deleted vertex: take the two smallest entries in that vertex’s row.
If LB = UB, you’ve solved the TSP exactly — this is a key examiner result.

⚠ Common mistakes

Using direct edge weights instead of shortest paths in the table — always check for indirect routes that beat the direct one.
Forgetting the return edge in NN — the route must close back to the starting vertex.
Confusing NN with Prim’s algorithm: NN forces a single chain (one selected value per column); Prim’s allows a tree structure.
Taking only one edge from the deleted vertex — you need two (cycle enters and leaves v).
Best UB = highest, best LB = lowest — backwards! The tightest sandwich uses the lowest UB and the highest LB.

Chapter complete — you now have the full Graph Theory toolkit: introduction (vertices, edges, degrees), walks & adjacency matrices, minimum spanning trees (Kruskal’s & Prim’s), the Chinese postman problem, the travelling salesman problem, and bounding techniques via Nearest Neighbour and Deleted Vertex. Together these cover every Paper 1 & 2 graph-theory question on the AI HL syllabus.

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 →