Higher Level only, and the last sub-topic in Topic 3. It needs 3.14's vocabulary and nothing from 3.15, and it is the most procedural block on the whole course: carry out a method, then say what it proves.
Run nearest neighbour as a class, out loud, before anything is on the screen. Someone calls the cheapest road at each step and you write it up: B 4, E 3, D 5, C 2, home 9. Total 23. Ask whether that is the shortest tour. Almost everyone says yes, and the reason they give is that every single choice was the best one.
Then view 3. A–B–C–D–E–A, 22. Let the silence sit. The greedy argument sounded airtight and it is not, and the gap of 1 is small enough that nobody suspects the method until they are shown.
View 4 is the resolution, and it is the one to leave up: a number line with 20 and 23 marked and the answer trapped between them. That picture is what a student should have in their head when a question says "find an upper bound".
| Question | Answer |
|---|---|
| 1. Nearest neighbour from A | 4 + 3 + 5 + 2 + 9 = 23, on A-B-E-D-C-A. |
| 2. The optimal tour | 4 + 5 + 2 + 5 + 6 = 22. |
| 3. MST of B, C, D, E | CD 2 + BE 3 + BC 5 = 10. |
| 4. The lower bound | 10 + 4 + 6 = 20. |
| 5. What 23 proves | B. The optimum is at most 23, because a tour of that length exists. |
Note that DE is also 5, so Kruskal's third edge can be BC or DE and the weight is 10 either way. Say so if a student offers the other one; a markscheme accepts either, and the ambiguity is a feature of the numbers rather than a trap.
1 markThe algorithm carried out, with the choices in order.
1 markThe total, including the closing edge.
1 markNaming the kind of bound.
The third mark is the cheapest in Topic 3 and the most often dropped. "So the shortest tour is at most 23" is nine words. Make the class write it every single time, including on questions that do not obviously ask for it, because it costs nothing and the habit protects the answer mark too.
| They wrote | What happened |
|---|---|
| 14 on question 1 | Forgot the road home. The commonest error in the sub-topic, and expensive here because the missing edge is 9, the longest in the graph. Get them writing A at both ends of the route first. |
| 22 on question 1 | Gave the optimum where the algorithm's output was asked for. They may well have found it correctly; the question was about the method. |
| 56 | Added all ten weights. They have not understood that a tour uses five edges. |
| 16 on question 2 | The four edges without the closing one. Same omission as 14, one question later. |
| 15 on question 3 | Four edges in the spanning tree. Four vertices need three, and the fourth edge closes a cycle. Ask them to draw it and find the cycle. |
| 30 | Every edge among B, C, D, E. The word "tree" has not landed. |
| 10 on question 4 | Stopped at the spanning tree. The two edges at A are the step that makes it a bound on a TOUR rather than on a tree. |
| 14 on question 4 | Added one edge at A instead of two. Worth a sentence: a tour arrives at A and leaves it, so A contributes two edges. |
| 21 | Used AB 4 and AD 7. The two CHEAPEST at A are 4 and 6; AD at 7 is dearer than both. |
"So what IS the shortest tour?" On this graph, 22, and the honest answer is that we found it by trying all of them. There are 12 distinct tours of five towns and a computer checked every one. No method on this syllabus finds it, and saying so plainly is better than implying the bounds are a shortcut to something the course could do properly.
"Why two edges at A in the lower bound?" Because any tour must come into A and go out of A, so it contains at least two edges at A, and the rest of the tour connects the other four towns, which costs at least the minimum spanning tree. Add the two cheapest possible and nothing has been overestimated. That paragraph is the justification and it is worth giving once, because without it the algorithm is four arbitrary steps.
"Euler or Hamilton?" Edges or vertices. The postman walks every road, so Euler. The salesman visits every town, so Hamilton. Write those two sentences on the board and leave them there for the lesson; questions swap the two words and nothing else.
"Does the starting town change the nearest neighbour answer?" In general yes, and the better bound is the smaller one. On this graph every start happens to total 23, which is worth knowing before you set it as an exercise. They are not all the same tour: A, B and C each walk A-B-E-D-C-A, while D gives D-C-B-E-A-D and E gives E-B-A-D-C-E, two further tours that also come to 23. If you want the bound itself to move, alter one weight. A question that names a starting vertex wants that one.
"Can the two bounds be equal?" Yes, and then you have proved the optimum, which is the only situation in which these algorithms settle the problem. Worth mentioning, because it tells students what the bounds are for.
| Stage | What to do |
|---|---|
| Demonstrate | Put both tours on one screen: 4+3+5+2+9 and 4+5+2+5+6, giving 23 and 22. Two lines, one above the other, is the most convincing form of the lesson, because the arithmetic is beyond dispute and the conclusion follows without any argument from you. |
| Where they stick | Nothing technical; the difficulty is behavioural. Students look for a graph-theory tool and there is not one on either machine. Say at the start that the calculator's only job in 3.16 is adding five numbers, and that the method goes on paper with edges ticked off as they are used. |
| The check | Count the edges in the answer. A tour of 5 towns uses 5 edges; a spanning tree on 4 vertices uses 3. If the sum on the page has four terms where five belong, the road home is missing. It is a two-second check and it catches the 14 and the 16 both. |
No angle mode, no matrices, no graphing. This is the one sub-topic in Topic 3 where a student with a broken calculator loses almost nothing.
| Step | What |
|---|---|
| 1 | Walk, trail, path, circuit, cycle, as five words against one drawing. |
| 2 | Euler: the odd-vertex test, tried on three small graphs. Edges. |
| 3 | Hamilton: vertices, and no test at all. Say that out loud; it motivates everything after it. |
| 4 | Kruskal on the four-town subgraph. Three edges, 10. |
| 5 | Nearest neighbour as a class, out loud. 23. Ask if it is shortest. |
| 6 | Figure view 3: 22. Silence. |
| 7 | Deleted vertex, with the two-edges-at-A reason given properly. 20. |
| 8 | View 4, the number line, and the sentence that goes with it. |
| 9 | Chinese postman on the second graph: odd vertices A and C, pair them for 7, total 32. |
Do not say "nearest neighbour finds the shortest route". It is the sentence this page exists to prevent, and students who hear it once will write 23 as the answer for the rest of the year. Say "nearest neighbour builds a tour, so it gives an upper bound", every time, with the conclusion attached to the method.
Do not say "the bounds give you the answer". They give you an interval. Here it is 20 to 23 and the answer is 22, which is in the interval and is not either end of it. A student who thinks bounds are a slower route to a single number will write the wrong one with confidence, and confidence is the expensive part.