Free IB Maths AI HL lesson: Travelling salesman problem: upper & lower bounds
A ready-to-teach IB Maths AI HL lesson on Travelling salesman problem: upper & lower bounds (Unit 3 · Geometry & Trigonometry): editable slides and teacher notes, free; a printable worksheet in 3 levels with answers for school plans. About 55 minutes.
Free with a teacher account. Sign in with Google, Microsoft or email and download the slides and teacher notes.
What's inside
- Slides (PowerPoint, editable) · freeabout 12 slides: do now, objectives, key ideas, a worked example step by step, “your turn”, practice QR code, exit ticket
- Teacher notes (PDF) · freelesson plan with timings, common mistakes, homework links
- Worksheet (PDF) · school plans5 questions, 24 marks: Fluency, Reasoning, Exam-style. Included with school plans and the teacher trial.
- Answers (PDF) · school plansthe answer to every worksheet question, from its mark scheme. Included with school plans and the teacher trial.
Learning objectives
- The Travelling Salesman Problem — Upper Bounds (Nearest Neighbour)
- Lower Bounds — the Deleted-Vertex Algorithm
- Travelling Salesman — Tables of Least Distances
Key ideas on the slides
- A value rounded to the nearest unit u lies within half a unit either side: 8.4 to 1 d.p. has bounds 8.35 and 8.45, written 8.35 ≤ x < 8.45.
- For a sum or product use upper with upper for the maximum and lower with lower for the minimum.
- For a difference or quotient, the maximum uses upper − lower and upper ÷ lower; the minimum uses lower − upper and lower ÷ upper.
- To give an answer to a suitable accuracy, round both bounds and use the value they agree to.
By the end of the lesson, students should be able to answer a question like: Use the nearest-neighbour algorithm from A to find an upper bound.
Key vocabulary
- upper bound: The largest value the measurement could have been before it was rounded.
- lower bound: The smallest value the measurement could have been.
- error interval: The inequality LB ≤ x < UB giving all the possible values.
- percentage error: The error as a percentage of the exact value.
Common mistakes this lesson tackles
- Graph algorithms: Prim vs nearest neighbour, no method shown, bounds mixed up. Show the algorithm: list edges in the order chosen, with weights, and say when it stops. Upper bound (nearest neighbour): best = smallest found. Lower bound (deleted vertex): MST of the rest + two shortest edges to the deleted vertex; best = largest found.
- Writing the upper bound as 8.449 or 8.4499…: the upper bound is 8.45.
- Using upper ÷ upper to find the largest possible quotient.
- Dividing by the approximate value in a percentage error.
The worked example
A delivery driver must visit 5 towns (A, B, C, D, E) and return to the start. The graph of the distances is fully connected. Removing vertex A and all its incident edges leaves a residual graph whose minimum spanning tree has a weight of 28 km. The two shortest edges connected to vertex A are 8 km and 11 km. Calculate the lower bound for the Travelling Salesman Problem.
- Identify the correct formula for the lower bound of the Travelling Salesman Problem (TSP): Weight of Residual MST + sum of the two shortest edges incident to the removed vertex.
- Extract the given weight of the residual minimum spanning tree: 28 km.
- Identify the lengths of the two shortest incident edges to vertex A: 8 km and 11 km.
- Sum these three values to calculate the lower bound: 28 + 8 + 11.
- The lower bound for the optimal tour is 47 km.
Tip: The lower bound for the Travelling Salesman Problem is often not a valid closed tour itself, but it guarantees that no valid Hamiltonian cycle can possibly have a shorter distance.
Calculator tips
- Keep the bound values exact on the calculator; do not round them before the final step.
- No GDC step: set out the tour and the tree clearly.
Lesson plan
| 0–5 min | Do now: students write down what they remember about Minimum spanning trees (Kruskal's & Prim's algorithms) and Route inspection & the Chinese postman problem |
| 5–8 min | Share the learning objective and success criteria |
| 8–20 min | Teach: the worked example, step by step; students copy the method |
| 20–25 min | Your turn: 1 mini-whiteboard question; check every board before moving on |
| 25–42 min | Practise: the worksheet (5 questions in 3 levels, with school plans and the teacher trial) or the topic's practice questions online; move up a level after two right in a row |
| 42–47 min | Plenary: 1-question exit ticket; collect it to plan the next lesson |
For students: practise this topic
The worksheet's QR code opens the IB Maths AI HL Unit 3: Graph Theory practice questions.
What schools get
- Set this lesson as homework, marked by AI against the mark scheme, with every result in your markbook (with a School plan).
- This lesson's worksheet in three levels, with its answers, ready to print.
- Support, Core and Stretch versions and A/B copies of the worksheet from the full question bank, in the worksheet builder.
- Create lesson: this lesson rebuilt for your class's next scheme-of-work lesson, from the full bank.
School licences from €490 a year. Try everything free for 30 days as a teacher: no card.
Questions teachers ask
Is this lesson free?
The slides and the teacher notes are free to download with a free IB Math Revision teacher account (sign in with Google, Microsoft or email); no card. The printable worksheet in three levels and its answers are included with school plans and the free 30-day teacher trial.
Can I edit the slides?
Yes. The slides are an ordinary PowerPoint file: change, add or delete anything. They also open in Google Slides and Keynote. The logo and web address sit on the slide master, so your edits do not move them.
What do students use for homework?
The practice slide's QR code and web address take students to the IB Maths AI HL Unit 3: Graph Theory practice questions on ibmathrevision.com, where the free questions are open and the full bank comes with a plan.