Mathematics Standard • Year 12 • Module 5 • Lesson 7
Kruskal's Algorithm — Past-Paper Style
Practise HSC-style short and extended responses on minimum spanning trees and Kruskal's algorithm.
1. Short-answer questions
1.1 A network has 8 vertices. Explain in one sentence how many edges any MST must contain, and state the sum of degrees of vertices in that MST. 2 marks Band 3
1.2 Apply Kruskal's algorithm to the following network. State the MST edges and the total cost.
Vertices A, B, C, D, E. Edges: AB = 6, AC = 4, AD = 9, BC = 3, BD = 8, BE = 7, CD = 2, CE = 5, DE = 1.
Show your sorted list and your add/reject decisions. 3 marks Band 3-4
1.3 A company costs five fibre links between four buildings P, Q, R, S as PQ = 8, PR = 4, PS = 9, QR = 5, QS = 6, RS = 7. (a) Use Kruskal's to find the MST and its cost. (b) The PR link is taken off the table. Find the new MST cost. (c) State, with reason, whether removing PR causes the MST cost to increase or decrease. 4 marks Band 4
Stuck on 1.3(c)? Removing a cheap edge can only make Kruskal's reach for a more expensive replacement — the new MST is never cheaper.2. Extended response
2.1 A regional council in NSW is planning a fibre-to-the-premises rollout linking six small towns: Armidale (A), Bingara (B), Coonabarabran (C), Dubbo (D), Eden (E) and Forbes (F). The proposed cable costs in $thousands are:
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | — | 15 | 22 | — | — | — |
| B | 15 | — | 9 | 18 | — | — |
| C | 22 | 9 | — | 11 | — | 14 |
| D | — | 18 | 11 | — | 13 | 16 |
| E | — | — | — | 13 | — | 10 |
| F | — | — | 14 | 16 | 10 | — |
(a) Use Kruskal's algorithm. List the edges in sorted order, then show each add/reject decision with reasons.
(b) State the MST edges and the total minimum cost.
(c) The council has a working budget of $60 thousand. A planning officer suggests adding the next-cheapest unused edge as a "back-up" link in case of damage. Identify that edge, give the new total cost, and write a one-sentence conclusion stating whether the council can still meet the budget. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — correctly sorts all 9 edges by weight.
• 1 mark — clearly logs each add/reject decision with components or cycle reason.
Part (b) — 2 marks
• 1 mark — correct list of 5 MST edges.
• 1 mark — correct total cost with units ($thousand).
Part (c) — 3 marks
• 1 mark — identifies the next-cheapest unused edge.
• 1 mark — correct new total cost.
• 1 mark — explicit conclusion sentence comparing total to $60k budget.
Your response:
Stuck? Read the matrix once and list every distinct edge with its weight before sorting.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Edges and sum of degrees in an MST on 8 vertices (2 marks)
Sample response. An MST on n vertices is a tree, which always has n − 1 edges; for n = 8 that is 7 edges. By the handshaking lemma, sum of degrees = 2 × edges = 2 × 7 = 14.
Marking notes. 1 mark — correct number of edges (7). 1 mark — correct sum of degrees (14) with reference to the lemma or to "2 × edges".
1.2 — Kruskal's on A,B,C,D,E (3 marks)
Sample response.
Sort: DE(1), CD(2), BC(3), AC(4), CE(5), AB(6), BE(7), BD(8), AD(9).
Add DE(1) → {D,E}. Add CD(2) → {C,D,E}. Add BC(3) → {B,C,D,E}. Add AC(4) → {A,B,C,D,E}. Stop (4 edges = 5 − 1). Remaining edges all form cycles.
MST edges: DE, CD, BC, AC. Total = 1 + 2 + 3 + 4 = 10.
Marking notes. 1 mark — sorted edge list. 1 mark — correct accept/reject logic with components. 1 mark — correct edges and total.
1.3 — Kruskal's, edge removal, comparison (4 marks)
(a) Sample response. Sort: PR(4), QR(5), QS(6), RS(7), PQ(8), PS(9). Add PR(4) → {P,R}. Add QR(5) → {P,Q,R}. Add QS(6) → {P,Q,R,S}. Stop (3 edges = 4 − 1). MST: PR, QR, QS; total = 4 + 5 + 6 = $15.
(b) Sample response. Without PR: sort QR(5), QS(6), RS(7), PQ(8), PS(9). Add QR(5), QS(6), then PQ(8) → {P,Q,R,S}. MST: QR, QS, PQ; total = 5 + 6 + 8 = $19.
(c) Sample response. Removing PR increases the MST cost (from $15 to $19) because Kruskal's must substitute the cheap PR edge with a more expensive replacement (PQ at $8 instead of PR at $4); a new MST is never cheaper than the original when an edge is removed.
Marking notes. (a) 1 mark — correct MST; 1 mark — correct cost. (b) 1 mark — correct new MST cost. (c) 1 mark — explicit "increases" with reason. Common error: assuming the cost stays the same after removing a low-weight edge.
2.1 — Regional fibre rollout (7 marks): sample Band-6 response with annotations
Sample Band-6 response.
(a) Sorted edge list and add/reject log.
Edges from matrix: AB = 15, AC = 22, BC = 9, BD = 18, CD = 11, CF = 14, DE = 13, DF = 16, EF = 10. Sort: BC(9), EF(10), CD(11), DE(13), CF(14), AB(15), DF(16), BD(18), AC(22). [1 mark — sorted list of all 9 edges.]
Add BC(9) → {B,C}. Add EF(10) → {B,C} and {E,F}. Add CD(11) → {B,C,D}. Add DE(13) → merges {B,C,D} and {E,F} → {B,C,D,E,F}. Reject CF(14) — forms cycle C–D–E–F–C. Add AB(15) → {A,B,C,D,E,F}. Stop (5 edges = 6 − 1). Remaining edges (DF, BD, AC) all form cycles. [1 mark — each decision logged with component or cycle reason.]
(b) MST and total cost.
MST edges: BC, EF, CD, DE, AB. [1 mark — correct edges.]
Total cost = 9 + 10 + 11 + 13 + 15 = $58 thousand. [1 mark — correct total with units.]
(c) Back-up link analysis.
Next-cheapest unused edge = CF (cost $14k). [1 mark — identifies CF.]
New total cost = $58k + $14k = $72 thousand. [1 mark — correct new total.]
Conclusion: with the back-up CF link added, the rollout costs $72 thousand, which exceeds the council's $60 thousand budget by $12 thousand, so the council cannot afford the back-up under the current budget. [1 mark — explicit conclusion comparing $72k to $60k.]
Total: 7/7.
Band descriptors for marker.
Band 3: Lists most edges and attempts sorting; identifies some MST edges but with a cycle or missing vertex; no clear cost. ≈ 3 marks.
Band 4: Full sorted list, all add/reject decisions shown, correct MST and total cost; part (c) attempts the back-up but uses wrong edge or fails to compare to budget. ≈ 4-5 marks.
Band 5: Complete (a) and (b), correct back-up identified and new total computed, but conclusion is bare numbers (no "exceeds budget" sentence). ≈ 6 marks.
Band 6: All parts complete with explicit conclusion sentence naming dollar amount, comparison to $60k, and statement that the budget is exceeded. 7/7.