Free IB Maths AI HL lesson: Minimum spanning trees (Kruskal's & Prim's algorithms)
A ready-to-teach IB Maths AI HL lesson on Minimum spanning trees (Kruskal's & Prim's algorithms) (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 plans6 questions, 26 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
- Minimum spanning trees: Kruskal's and Prim's algorithms
Key ideas on the slides
- A minimum spanning tree connects every vertex with the least total weight, using n − 1 edges and no cycles.
- Kruskal: sort edges by weight; add the smallest that does not make a cycle; stop at n − 1 edges.
- Prim: start at any vertex; repeatedly add the smallest edge joining a vertex in the tree to one outside it.
- Prim's algorithm on a table: cross out the row of each new vertex, look down the chosen columns for the smallest entry.
By the end of the lesson, students should be able to answer a question like: Use Kruskal's algorithm to find the minimum spanning tree and its weight.
Key vocabulary
- spanning tree: A tree that includes every vertex of the graph.
- minimum spanning tree: A spanning tree with the least total weight.
- weight: The number on an edge (distance, cost, time).
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.
- Adding an edge that forms a cycle.
- Using nearest neighbour (a tour) instead of Prim.
- Not stating the order of selection.
The worked example
A connected, weighted graph has edges with the following weights: AB=4, AC=5, BC=6, BD=3, CD=4, CE=7, DE=2. Using Kruskal's algorithm, find the total weight of the minimum spanning tree.
- List all edges in ascending order of their weights: DE (2), BD (3), AB (4), CD (4), AC (5), BC (6), CE (7).
- Select the smallest edge, DE, with weight 2.
- Add the next smallest edges, BD (3) and AB (4), as they do not form cycles.
- Reject the edge CD (4) because connecting C, D, and B would form a closed cycle.
- Add edge AC (5) to connect vertex C to the tree without forming a cycle. All 5 vertices (A, B, C, D, E) are now connected.
- Sum the selected edge weights: 2 + 3 + 4 + 5. The total weight of the minimum spanning tree is 14.
Tip: Always physically cross out edges that form a cycle on your working paper so you do not accidentally include them in your final minimum spanning tree sum.
Calculator tips
- No GDC step: keep a list of edges in order.
Lesson plan
| 0–5 min | Do now: students write down what they remember about Route inspection & the Chinese postman problem and Eigenvalues & PageRank-style centrality |
| 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 (6 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.