At a glance. One lesson of about 60 minutes. It builds on graphs and routes. Students find a shortest path by listing routes or working outwards, find a minimum spanning tree by taking cheap edges that make no cycle, and tell which tool a problem needs.
Calculator: no calculator. No calculator: weights are small whole numbers added by hand, and the skill is the order in which edges are considered.
What students will learn
Know
- A weighted graph has a number on every edge.
- A tree is a connected graph with no cycle and n vertices have n − 1 edges.
- Take edges in order of weight and skip any that close a cycle.
Understand
- Why more edges can mean a shorter route.
- Why a spanning tree has exactly n − 1 edges.
- Why a minimum spanning tree and a shortest-route tree are different.
Do
- Find the shortest route in a small weighted graph.
- Build a minimum spanning tree and give its weight.
- Choose between the two tools for a context.
MYP assessment criteria
Wording paraphrased. What this lesson gives you evidence for, and what to look for:
- Criterion A. Knowing and understanding: the definitions of tree and spanning tree and the two procedures (questions 1 to 8).
- Criterion B. Investigating patterns: the figure. Students compare the route to a vertex with the tree and describe when they differ.
- Criterion C. Communicating: listing the edges considered, taken and skipped in a clear table.
- Criterion D. Applying mathematics in real-life contexts: pipes, cables and roads (hook and questions 2, 3, 4, 5 and 7).
The one thing to do with the figure
Ask for the prediction first. Then step through the destinations with the route shown, and ask which edges the route to F uses before switching to the tree.
Ask: “Which edges are in the tree but not on the route to F, and which are on the route and not in the tree?” Listen for: DE and EF are in the tree and not on the route; DF is on the route and not in the tree; AB, CD and CE are in neither.
A possible order
| 5 min | Warm-up from the student page, in silence, then answers. |
|---|---|
| 5 min | Hook: the water board and the courier; collect predictions. |
| 12 min | Figure, key idea and warning card; compare the route to F with the tree. |
| 8 min | Worked examples; pairs finish the faded example. |
| 5 min | Question 1, the check. If many choose B, ask whether the tree has to give the shortest route from P. |
| 20 min | Your turn, Levels 1 to 3, at each student's own pace. |
| 5 min | Something to think about, then the exit ticket, question 8. |
The answers
| Warm-up | 22; 18; no. |
|---|---|
| Hook | No. The route from A to F has length 13, and the cheapest tree has weight 14. The tree must reach every village, and the route only has to reach one. |
| Worked examples | Length 7; weight 9; 8 edges. |
| Faded example | Length 5 (S, U, T). |
| 1. Building a minimum spanning tree | C. A keeps a cycle and misses T; B is the shortest-route tree; D has one edge too many. |
| 2. Edges in a tree | 12. 11 + 1. |
| 3. Minimum spanning tree weight | 12. 3 + 4 + 5. |
| 4. Shortest path | 12. P, R, Q, S, T. |
| 5. Minimum spanning tree weight | 20. 2 + 3 + 4 + 5 + 6. |
| 6. Adding a constant to every edge | 49. 31 + 6 × 3. |
| 7. When every edge grows | 19. P, Q, T or P, Q, S, T. |
| 8. Choosing and using the right tool | A. B pipes each field from the tank; C keeps a cycle; D reaches one field. |
What each wrong answer tells you
| They give | What it usually means | What to do |
|---|---|---|
| A, B or D in question 1 | Took the cheapest edges without the cycle test, built shortest routes from one vertex, or kept n edges. | Ask: which edges close a cycle? How many edges does a tree on 5 vertices have? |
| 11 or 10 in question 2 | Gave the number of roads, or took 1 away instead of adding it. | Ask: in a tree, are there more villages or more roads, and by how many? |
| 18 or 13 in question 3 | Added the four cheapest edges, or built a tree of shortest routes from one town. | Ask which cable is skipped and why. |
| 15 or 14 in question 4 | Took the route with the fewest roads, or used the long road RS. | Make a table of routes with their lengths and compare. |
| 19 or 25 in question 5 | Added the five cheapest links without testing for a cycle, or used six links. | Ask: do UV, UW and VW form a triangle? Can all three be used? |
| 34 or 52 in question 6 | Added the increase once, or once per vertex. | Ask: how many edges does the tree contain? |
| 20 or 14 in question 7 | Kept the old route, or added the increase once. | Ask: how much longer does a route of 4 roads get, and a route of 2 roads? |
| B, C or D in question 8 | Piped each field from the tank, kept a cycle, or found one route. | Ask: can water flow from one field on to the next? Which pipe closes a cycle? |
Questions worth asking
- Why does a spanning tree on n vertices have n − 1 edges? Listen for: each new vertex needs one new edge, and an extra edge would make a cycle.
- Is the shortest route always the one with the fewest edges? Listen for: no, several short edges can beat one long edge.
- Why can you skip an edge in Kruskal's method? Listen for: its ends are already joined, so adding it would make a cycle.
- If I make every edge 3 longer, does the shortest route change? Listen for: it can, because routes with more edges gain more; the tree does not change.
Differentiation
A way in for anyone stuck
- Give a printed graph with a table: edge, weight, take or skip, and total.
- Provide the graph on a grid with edge weights and a coloured pencil for the chosen edges.
- Give the frame: “I take … because …. I skip … because it joins … and …, which are already joined.”
Stretch
- Show that if every edge weight is different, the minimum spanning tree is unique.
- Give a graph where the shortest route from A to B does not use the cheapest edge at A.
Students learning in English as an additional language
“Weight” here means the number on an edge, which may be a distance or a cost. “Span” means to reach every vertex. “Cycle” means a route that comes back to where it started. “Skip” means to not use an edge.
| Word | Plain meaning | Example |
|---|---|---|
| weighted graph | a graph with a number on each edge | road lengths in kilometres |
| tree | a connected graph with no cycle | a branching river system |
| spanning tree | a tree that includes every vertex | pipes to every house |
| shortest path | the route with the least total weight between two vertices | the quickest drive |
| cycle | a route that returns to its starting vertex | a ring road |
Sentence starters for explaining aloud or in writing:
- I take the edge … because it has weight … and does not close a cycle.
- I skip the edge … because … and … are already joined.
- The route through … is shorter because …
Two things not to say
“The shortest path is the one with the fewest roads.” Say instead: the shortest path has the least total length, and that may need more roads.
“A minimum spanning tree gives the shortest route between every pair.” Say instead: it gives the least total weight that joins every vertex.
Questions to set
Extra practice in three tiers, including one question from earlier work for spacing. Every answer has been checked.
1Fluency
The idea on its own, with friendly numbers. Set these first.
- FindHow many edges has a spanning tree of a graph on 10 vertices?
9. - FindRoutes A to B cost 4 + 3 and 9. Which is shorter?
The two-edge route, 7.
2In context
The same idea inside a situation, where the first job is deciding what to calculate.
- ContextFour towns have possible cables AB 2, AC 5, BC 3, BD 4 and CD 6. What is the least cost to join them all?
AB 2, BC 3 and BD 4: 9. - Earlier work (lesson 1)A graph has 8 vertices and 12 edges. What do the degrees add to?
24.
3Challenge
Reasoning, generalizing and working backwards.
- ReasoningIn a connected graph with 6 vertices and 9 edges, how many edges must be removed to make a spanning tree?
4: 9 − 5. - Working backwardsA spanning tree on 8 vertices has weight 40 and each edge is made 2 shorter. What is the new weight?
40 − 7 × 2 = 26.
Practicalities
Works on a phone or a shared screen. Nothing a student types is saved or sent anywhere.
The figure works with the keyboard (tab to a slider, then the arrow keys) and by touch. “Show me the steps” gives the same states in words.
No calculator is needed.