Take the cheapest road at every step and you get 23. Every choice was the best available, and the tour is still not the best tour: the true shortest is 22.
Two tours of the same five towns, one built greedily and one optimal. They are not the same tour.
| Word | What it may repeat | Closed? |
|---|---|---|
| Walk | Anything: edges and vertices | Either |
| Trail | Vertices, but no edge twice | Either |
| Path | Nothing | Open |
| Circuit | Vertices, but no edge twice | Closed |
| Cycle | Nothing except the start, which is also the end | Closed |
| Named route | Visits | Exists when |
|---|---|---|
| Eulerian trail | every EDGE once | the graph is connected AND exactly 0 or 2 vertices have odd degree |
| Eulerian circuit | every EDGE once, and returns | the graph is connected AND every vertex has even degree |
| Hamiltonian path | every VERTEX once | no simple test exists |
| Hamiltonian cycle | every VERTEX once, and returns | no simple test exists |
Euler is about edges and Hamilton is about vertices. The two words are the thing questions swap on you. Connectivity sits in both Euler rows for a reason: two disjoint triangles have every degree even and no Eulerian circuit at all. And note the asymmetry: Euler has a five-second test and Hamilton has none at all, which is the whole reason the travelling salesman problem needs bounds instead of an answer.
A spanning tree reaches every vertex with no cycles, so on n vertices it has n − 1 edges. The minimum one is the cheapest such. Two algorithms, same answer:
On the four towns B, C, D, E, Kruskal takes CD = 2, then BE = 3, then needs to join those two pieces and takes BC = 5 (or DE = 5, the same weight). Three edges for four vertices, total 10.
Prim from a matrix, which is the version the syllabus names. Write the weights as a table, start at a town, and repeat: cross out that town's row, then look down every column you have not yet crossed out and take the smallest entry in the rows you have. On all five towns, starting at A:
Four edges for five towns, total 14. Prim never has to check for a cycle, because the tree stays connected and you only ever reach outwards, which is exactly why the matrix version works mechanically.
A table of least distances comes first. The salesman problem as stated above needs a complete graph: every pair of towns joined, so that any order of visits is a real tour. A practical map is rarely complete, and some direct roads are longer than going via a third town. So replace every entry by the shortest route between those two towns, however many roads it uses, and work on that table. Skipping this step is the commonest way to get a correct algorithm applied to the wrong numbers.
No efficient algorithm for the shortest tour is known, so the syllabus asks you to trap it between two numbers.
Nearest neighbour, for an UPPER bound. From A, go to the nearest unvisited town each time, then return home:
Total 23. Every step was the cheapest available, and the forced return edge of 9 is what ruins it. A real tour exists with length 23, so the optimum is at most 23. That is all nearest neighbour ever claims.
Deleted vertex, for a LOWER bound. Delete A, find the minimum spanning tree of what is left, then add back the two cheapest edges at A:
MST of B, C, D, E = 10, two cheapest at A: AB = 4 and AE = 6, so 10
Lower bound = 10 + 10 = 20.
A is not special. Delete any vertex you like and the same method gives a bound. Here deleting B also gives 20, and deleting C, D or E each gives 19. All five are valid lower bounds, so the largest of them is the useful one, which is why 20 is the one quoted. A question that names the vertex to delete wants that one.
So the shortest tour is between 20 and 23. It is in fact 22, on A–B–C–D–E–A, which no algorithm on this syllabus would have found.
Nearest neighbour is not wrong; it is an upper bound. The distinction is the whole sub-topic. If a question asks for an upper bound, 23 is the full answer and is correct. If it asks for the shortest tour, 23 is incorrect. Read which one is being asked for before you start, and if the question asks for both bounds, say explicitly that the optimum lies between them rather than naming either as the answer.
Here you must walk every edge and come back, so this is Euler, not Hamilton. Take a graph with AB = 5, BC = 4, CD = 6, AD = 3, AC = 7, total weight 25.
If every vertex had been even, the answer would have been 25 exactly, with nothing repeated. The extra is the price of the odd vertices, and there is always an even number of them, which is the handshake lemma from 3.14 doing useful work.
With four odd vertices you have to compare the pairings. Four odd vertices W, X, Y and Z pair up in exactly three ways: WX with YZ, WY with XZ, or WZ with XY. Cost each pairing as the sum of its two shortest paths and take the cheapest of the three. The syllabus goes up to four odd vertices and stops, precisely because three is a short enough list to check by hand. Naming one pairing without comparing it with the other two loses the method mark, even when it turns out to be the cheapest.
Neither machine implements any of these algorithms. That is not an oversight: the point of 3.16 is that you carry out a procedure and state what it proves, and a button would remove the only thing being assessed.
When you may use it. Applications. A calculator is allowed in every paper and it has one job here: adding four or five weights without slipping. Do that, and do the algorithm on paper with the edges crossed off as you use them.
The mark people lose. Forgetting the edge home. On the nearest neighbour route the four steps total 14 and the return from C to A is 9, which is the single most expensive edge in the graph and the one you have no choice about. 14 is the commonest wrong answer here and it is 9 short. Write the starting town at both ends of your route before you add anything up, so the final edge is on the page before the arithmetic starts.
Weights: AB 4, AC 9, AD 7, AE 6, BC 5, BD 8, BE 3, CD 2, CE 7, DE 5.
1. Apply nearest neighbour starting at A. What is the total length of the tour?
2. The tour A–B–C–D–E–A is the shortest there is. How long is it?
3. Delete A. What is the weight of the minimum spanning tree of B, C, D and E?
4. Finish the deleted vertex algorithm. What is the lower bound?
5. Nearest neighbour returned 23. What have you proved?
1 markThe algorithm carried out, with the choices shown in order.
1 markThe total, including the edge home.
1 markSaying which kind of bound it is.
That third mark is free and it is the one most often missed. Writing "so the shortest tour is at most 23" takes one clause, and writing "the shortest tour is 23" loses the mark and makes a false claim.
These pages are free and stay free, but they are general and your IA is not. Send me your research question, or whatever exists so far, and I will tell you in writing whether the topic has a ceiling on it, where the marks are going, and what to change first. That costs nothing and it comes back within 24 hours.
Written by a serving IB Diploma and Career-related Programme Coordinator and Head of Mathematics, who reads internal assessments across every subject group every year. If you then want the whole draft reviewed properly against all five criteria, that is the paid one, and it is refunded if it does not name at least three specific things to fix.
Already have a full draft? Have the whole thing reviewed against all five criteria, $99.