Mathematics Standard • Year 12 • Module 5 • Lesson 7
Kruskal's Algorithm — Skill Drill
Build fluency in the Kruskal's recipe: sort the edges, add cheapest, skip cycles, stop at n − 1 edges. Track components and compute the MST total weight.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Complete the definition:
A minimum spanning tree (MST) is a spanning tree with the ______________________ total edge weight.
Q1.2 Write the four steps of Kruskal's algorithm in order:
1. ____________________ 2. ____________________ 3. ____________________ 4. Stop after ____ edges.
Q1.3 A network has 9 vertices. How many edges will the MST contain? ____
2. Worked example — Kruskal's in action
Follow every line. Each step has a reason on the right.
Problem. Five towns A, B, C, D, E have roads with costs (in $millions): AB = 5, AC = 8, BC = 6, BD = 4, CD = 7, CE = 9, DE = 3. Find the MST and its total cost.
Step 1 — Sort the edges from smallest to largest.
DE(3), BD(4), AB(5), BC(6), CD(7), AC(8), CE(9)
Reason: Kruskal's always picks the cheapest unused edge next.
Step 2 — Add cheapest, skip any that forms a cycle. Track components.
DE(3) add → components {D,E}
BD(4) add → components {B,D,E}
AB(5) add → components {A,B,D,E}
BC(6) add → components {A,B,C,D,E} — 4 edges, all 5 vertices ✓ stop
CD(7) reject → forms cycle B–C–D–B
AC(8) reject → forms cycle
CE(9) reject → forms cycle
Reason: an edge inside an existing component would close a loop, which a tree cannot have.
Step 3 — Sum the chosen edges.
Total = 3 + 4 + 5 + 6 = 18
Conclusion. MST edges: DE, BD, AB, BC. Total cost = $18 million.
3. Faded example — fill in the missing steps
Network: A, B, C, D, E with edges AB = 7, AC = 3, AD = 6, BC = 4, BD = 2, CD = 5, CE = 8, DE = 1. Apply Kruskal's. 4 marks
Step 1 — Sort: DE( __ ), BD( __ ), AC( __ ), BC( __ ), CD( __ ), AD( __ ), AB( __ ), CE( __ ).
Step 2 — Add or reject (track components):
DE(1) ______ components: {____}
BD(2) ______ components: {____}
AC(3) ______ components: {____}, {____}
BC(4) ______ components: {____}
CD(5) ______ reason: ____________
AD(6) ______ reason: ____________
CE(8) ______ components: {____}
Step 3 — Sum: Total = ____ + ____ + ____ + ____ + ____ = ____
Conclusion. MST has ____ edges (= n − 1 = ____). MST total = ____.
4. Graduated practice — apply Kruskal's
Show working below each part. Sort first, then add or reject.
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | A connected network has 12 vertices. How many edges are in any MST? | |
| 4.2 1 | List in sorted order: 6, 1, 4, 2, 7, 3. | |
| 4.3 1 | True / False: Kruskal's may reject an edge even if it is the cheapest remaining. | |
| 4.4 1 | Kruskal's adds edges with weights 2, 3, 5, 7. What is the MST total? |
Standard — typical HSC difficulty (6 questions)
Show one line of sorted edges and one line per add/reject.
4.5 Apply Kruskal's to vertices A, B, C, D with edges AB = 6, AC = 2, AD = 5, BC = 3, BD = 4, CD = 1. State MST edges and total. 2 marks
4.6 Apply Kruskal's to vertices A, B, C, D, E with edges AB = 4, AC = 6, BC = 2, BD = 5, CD = 3, DE = 1, CE = 7. 2 marks
4.7 A network has six vertices. Kruskal's accepts edges with weights 3, 4, 4, 6, 8 in order. Find the MST total. 2 marks
4.8 Apply Kruskal's to a five-vertex network with AB = 9, AC = 2, AD = 7, BC = 6, BD = 3, BE = 8, CD = 4, CE = 5, DE = 1. 2 marks
4.9 In a six-vertex network, Kruskal's chooses an edge of weight 5 as the third edge. The third edge connected two existing components. State, in one sentence, why this edge was not rejected. 2 marks
4.10 A network on vertices A, B, C, D, E has edges AB = 2, BC = 2, CD = 2, DE = 2, EA = 2, AC = 5. Find an MST and explain why it is not unique. 2 marks
Extension — combine ideas (2 questions)
4.11 A regional council plans fibre-optic cable between six towns with costs (in $thousands): AB = 12, AC = 7, AD = 15, BC = 9, BD = 14, BE = 6, CD = 11, CE = 13, DE = 5, DF = 10, EF = 8. (a) Use Kruskal's to find the MST. (b) State the minimum total cost to connect all six towns. 3 marks
4.12 A road agency has a budget of $30 million. The MST for the proposed network has total weight $26 million; the next cheapest edge to add would be $5 million. (a) Can the agency afford the MST? (b) Could the agency add the next-cheapest edge to give a back-up loop? (c) Briefly explain why adding any extra edge to an MST creates a cycle. 3 marks
5. Self-check the easy 3
Tick the first three once you have checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — MST definition
A minimum spanning tree is a spanning tree with the smallest possible total edge weight.
Q1.2 — Kruskal's steps
1. Sort edges by weight (smallest first). 2. Take the cheapest unused edge. 3. Add it if it joins different components; reject if it forms a cycle. 4. Stop after n − 1 edges.
Q1.3 — Edges in MST on 9 vertices
n − 1 = 9 − 1 = 8 edges.
Q3 — Faded example (8 edges, weights 1–8)
Sort: DE(1), BD(2), AC(3), BC(4), CD(5), AD(6), AB(7), CE(8).
DE(1) add → {D,E}. BD(2) add → {B,D,E}. AC(3) add → {A,C} and {B,D,E}. BC(4) add → {A,B,C,D,E}. CD(5) reject — forms cycle B–C–D–B. AD(6) reject — forms cycle A–C–B–D–A or similar. CE(8) add → {A,B,C,D,E} now includes E? E was already in. So CE forms a cycle too — reject. We needed n − 1 = 4 edges and we already have them after BC(4). Done.
Sum: 1 + 2 + 3 + 4 = 10. MST has 4 edges (n − 1 = 5 − 1 = 4). MST total = 10.
Q4.1 — Edges in MST on 12 vertices
n − 1 = 11 edges.
Q4.2 — Sorted weights
1, 2, 3, 4, 6, 7.
Q4.3 — Cheapest remaining can be rejected
True — if the cheapest unused edge has both endpoints in the same component, it forms a cycle and is rejected.
Q4.4 — MST total from accepted weights
Total = 2 + 3 + 5 + 7 = 17.
Q4.5 — Kruskal's on A,B,C,D with given weights
Sort: CD(1), AC(2), BC(3), BD(4), AD(5), AB(6). Add CD → {C,D}. Add AC → {A,C,D}. Add BC → {A,B,C,D}. Stop (3 edges = n − 1). MST edges: CD, AC, BC; total = 1 + 2 + 3 = 6.
Q4.6 — Kruskal's on A,B,C,D,E
Sort: DE(1), BC(2), CD(3), AB(4), BD(5), AC(6), CE(7). Add DE → {D,E}. Add BC → {B,C}. Add CD → {B,C,D,E}. Add AB → {A,B,C,D,E}. Stop (4 edges). MST: DE, BC, CD, AB; total = 1 + 2 + 3 + 4 = 10.
Q4.7 — MST total from accepted weights
3 + 4 + 4 + 6 + 8 = 25.
Q4.8 — Kruskal's on A,B,C,D,E with 9 edges
Sort: DE(1), AC(2), BD(3), CD(4), CE(5), BC(6), AD(7), BE(8), AB(9). Add DE → {D,E}. Add AC → {A,C}. Add BD → {A,C}, {B,D,E}. Add CD → joins {A,C} with {B,D,E} → {A,B,C,D,E}. Stop (4 edges). MST: DE, AC, BD, CD; total = 1 + 2 + 3 + 4 = 10.
Q4.9 — Why a weight-5 edge was accepted
Its two endpoints lay in different components, so adding it could not create a cycle — it simply merged the two components.
Q4.10 — MST on the 5-cycle with diagonal
Cycle A–B–C–D–E–A all weight 2; diagonal AC weight 5. Sort: any four edges of weight 2 will do. One MST: AB, BC, CD, DE (total = 8). Another: BC, CD, DE, EA (total = 8). Not unique because there are several edges of equal weight (5 edges of weight 2), and Kruskal's can pick any 4 of them that connect all vertices without a cycle.
Q4.11 — Six-town fibre network (11 edges)
Sort: DE(5), BE(6), AC(7), EF(8), BC(9), DF(10), CD(11), AB(12), CE(13), BD(14), AD(15). Add DE(5) → {D,E}. Add BE(6) → {B,D,E}. Add AC(7) → {A,C}, {B,D,E}. Add EF(8) → {B,D,E,F}, {A,C}. Add BC(9) → joins {A,C} with {B,D,E,F} → {A,B,C,D,E,F}. Stop (5 edges).
MST edges: DE, BE, AC, EF, BC. Total = 5 + 6 + 7 + 8 + 9 = $35 thousand.
Q4.12 — Budget and back-up loop
(a) MST total = $26m ≤ $30m budget, so yes they can afford it.
(b) Adding the next-cheapest edge would cost $26m + $5m = $31m > $30m, so no, not within budget.
(c) An MST has exactly n − 1 edges connecting all n vertices. Any extra edge connects two vertices that are already linked by a path in the tree, so adding it creates a cycle.