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.