• The problem itself: find the tour of least weight that visits every vertex and returns to the start — classical (visit each exactly once) vs practical (visit each at least once).
• Table of least distances: turns a messy, incomplete "practical" network into a complete "classical" one, using the triangle inequality.
• Upper bound: built from a minimum spanning tree, doubled, then improved with a "shortcut."
• Lower bound: built with the "deleted vertex method" — remove a vertex, find the residual minimum spanning tree, add back the two cheapest connections.
• Nearest neighbour algorithm: a quick greedy method that also gives an upper bound (a real route you can walk).
• Solving completely: for small graphs, list every possible Hamiltonian cycle and find the cheapest — or show a found route matches the lower bound, proving it's optimal.

Picture a delivery driver who has to visit six villages and get back to their depot, doing the least total driving possible. That's the whole problem in one sentence: find the tour of least weight in a network.

A tour is a walk that starts at one vertex, visits every other vertex, and returns to where it started. There are two flavours of this problem, and the difference is subtle but important:

Here's the key trick that ties them together: if you build a table of least distances for a practical network, you effectively turn it into a classical problem — because now every vertex has a direct "shortest path" connection to every other vertex, even if that path passes through other villages.

Think of this table as a "shortest possible commute" chart between every pair of villages — even ones with no direct road. Mathematically, every entry must satisfy the triangle inequality:

The 5-step method

1. Rule out the diagonal. Put a dash/line through every cell where a vertex meets itself — there are no loops.
2. Fill in direct connections for one vertex — its distance to every vertex it's directly joined to. Check by inspection that each is actually the shortest route (sometimes going the "long way round" beats the direct edge).
3. Fill the gaps — for vertices that aren't directly connected, find the shortest route between them by tracing through the network.
4. Copy the row into the matching column — the table is symmetric (undirected network), so whatever you found for row A also belongs in column A.
5. Repeat for the next vertex until the whole table is full.

Worked example

Six villages A–F are connected by roads of varying "walking time" weight. After applying the 5-step method (finding shortcuts like A→C→E = 13 instead of a longer direct route), the completed table looks like this:

Highlighted cells = calculated shortest paths (not direct edges), e.g. A→E = A→C→E = 7+6 = 13.

An upper bound is a "worst case that's still good" — it's a real, honest route you could actually walk, so we know for certain the true optimal answer is no worse than this number. The smaller you can make your upper bound, the more useful it is.

The 3-step method

1. Find the minimum spanning tree. Use Prim's algorithm if you have a table of least distances, or Kruskal's algorithm if you only have the graph.
2. Double the weight of the minimum spanning tree. This guarantees every vertex is visited and you get back to the start (walking each branch there-and-back).
3. Reduce the weight by finding a shortcut — replace a repeated "there and back" pathway with a single direct edge that isn't in the spanning tree, if one exists and is cheaper.

Worked example (same 6-village network)

Step 1 — Kruskal's algorithm (sort edges by weight, add smallest first, skip any edge that would create a cycle):

CD(5), CE(6), AC(7), EF(8), BF(9)  →  all 6 vertices connected, spanning tree complete

Step 2 — Double it:

Tree weight = 5+6+7+8+9 = 35  →  Initial upper bound = 35 × 2 = 70 minutes

Step 3 — Find a shortcut: The spanning tree forces you to repeat the path A→C→E→F→B (weight 30) there-and-back. But there's a single direct edge AB = 14 that isn't in the tree!

Saving = 30 − 14 = 16  →  Improved upper bound = 70 − 16 = 54 minutes

If the upper bound is "here's a route that definitely works," the lower bound is the opposite: "here's proof the answer can't possibly be cheaper than this." We want this number as high as possible, to squeeze the gap.

The 5-step method

1. Delete a vertex and all its edges from the network entirely.
2. Find the minimum spanning tree for what's left — this is called the residual minimum spanning tree (RMST). Note its total weight.
3. Reconnect the deleted vertex using its two cheapest individual edges back to the tree. Add their weights to the RMST total.
4. Repeat steps 1–3 by deleting a different vertex each time (if the question asks for the best possible lower bound).
5. Take the maximum of all the values you calculated — that's the best (tightest) lower bound.

Worked example — deleting vertex A

Step 1: Delete A and all its edges.

Step 2: Apply Prim's algorithm to the remaining B, C, D, E, F:

Edges added: BF(9), EF(8), CE(6), CD(5)  →  RMST weight = 9+8+6+5 = 28

Step 3: Reconnect A using its two shortest edges: AC(7) and AD(11).

Lower bound = 28 + 7 + 11 = 46 minutes

Now compare — deleting vertex E instead:

RMST (without E): AC(7), CD(5), BC(13), BF(9) = 34
Reconnect E with its two shortest edges: CE(6), EF(8)
Lower bound = 34 + 6 + 8 = 48 minutes

This is a much faster (but greedier) way to get an upper bound. Instead of building a spanning tree, you just walk to the closest unvisited village every single time, like a slightly lazy tourist who always picks the nearest attraction next. It won't always give the best route, but it's quick and always gives a valid, walkable tour.

The 5-step method

1. Choose a starting vertex.
2. Move to the nearest unvisited vertex from the current one (smallest weight edge). If tied, pick either. Cross out edges leading back to already-visited vertices so you never revisit them early.
3. Once every vertex has been visited, add one final edge back to the starting vertex to close the loop.
4. Add up all the edge weights in your Hamiltonian cycle — this total is your upper bound.
5. (Optional) Repeat from a different starting vertex each time, and keep the smallest total — that's the best possible upper bound from this method.

Worked example — starting at A

Tracing through the table, always picking the cheapest unvisited option:

A → C (7) → D (5) → E (10) → F (8) → B (9) → back to A (14)

Hamiltonian cycle: ACDEFBA

Total weight = 7 + 5 + 10 + 8 + 9 + 14 = 53 minutes

For small networks, you can brute-force it: list every possible Hamiltonian cycle and pick the cheapest. This isn't practical for big networks (a 6-vertex complete graph already has 120 possible cycles!), but it's the gold-standard method to prove a solution is optimal when combined with the bounds you've already found.

The "prove it's optimal" trick

You almost never actually check all 120 cycles by hand in an exam. Instead, the typical pattern is:

1. Find a lower bound (deleted vertex method) — say it's 53.
2. Find a specific route (often given, or found via nearest neighbour / by inspection) starting at the vertex specified.
3. Calculate that route's total weight.
4. If the route's weight equals the lower bound, you've proven it's optimal — nothing could possibly be cheaper, and you've found a real route matching that exact cost!

Worked example

Given a lower bound of 53 minutes, and starting at vertex A, we find the route:

AB(14) + BF(9) + EF(8) + CF... wait — route ABFECDA:
AB(14) + BF(9) + FE(8) + EC(6) + CD(5) + DA(11) = 53

Key Terms

Key Formulas / Rules

• I can explain the difference between the classical and practical TSP.
• I can construct a table of least distances using the 5-step method.
• I understand and can apply the triangle inequality to check a table of least distances.
• I can find an upper bound by doubling a minimum spanning tree and applying a shortcut.
• I know when to use Prim's algorithm vs Kruskal's algorithm for the spanning tree.
• I can find a lower bound using the deleted vertex method.
• I can compare lower bounds from deleting different vertices and pick the best (highest) one.
• I can apply the nearest neighbour algorithm to find an upper bound / Hamiltonian cycle.
• I understand the difference between nearest neighbour and Prim's algorithm.
• I can prove a route is optimal by matching its weight to the lower bound.
• I know why there's no efficient algorithm that guarantees the true optimal TSP solution.