Solutions — Minimum Spanning Trees — Grade 12 General Maths

Fluency A graph has 4 vertices. How many edges in a spanning tree?

A spanning tree with n vertices has exactly n−1 edges.
For n = 4: 3 edges

Fluency Kruskal’s on: AB=5, AC=3, BC=8, BD=2, CD=6.

Sorted edges: BD=2, AC=3, AB=5, CD=6, BC=8

Add BD=2: components {B,D}, {A}, {C} → ✓
Add AC=3: components {B,D}, {A,C} → ✓
Add AB=5: connects {A,C} and {B,D} → all 4 vertices connected. ✓ STOP

MST edges: BD, AC, AB Total weight = 2+3+5 = 10

Fluency Prim’s from A: AB=7, AC=4, AD=2, BC=3, CD=5.

Start at A. Available edges from A: AB=7, AC=4, AD=2.
Step 1: Add AD=2 (smallest). Tree: {A,D}.
Available: AB=7, AC=4 (from A), DC=5 (from D).
Step 2: Add AC=4 (smallest). Tree: {A,C,D}.
Available: AB=7, BC=3 (from C), DC already internal.
Step 3: Add BC=3 (smallest). Tree: {A,B,C,D}. Done.

MST edges: AD, AC, BC Total weight = 2+4+3 = 9

Fluency Spanning tree weights: 3, 5, 2, 8, 4.

Total weight = 3+5+2+8+4 = 22
(Note: a spanning tree with 5 edges connects 6 vertices.)

Understanding Telecommunications: 5 suburbs. Edges BC=4, AC=6, CE=7, BD=8, CD=9, AB=10, DE=11, BE=12, AD=15, AE=20.

Sorted edges: BC=4, AC=6, CE=7, BD=8, CD=9, AB=10, DE=11, BE=12, AD=15, AE=20

Add BC=4: {B,C} ✓
Add AC=6: {A,B,C} ✓
Add CE=7: {A,B,C,E} ✓
Add BD=8: {A,B,C,D,E} — all 5 connected. STOP (4 edges for 5 vertices).

MST edges: BC=4, AC=6, CE=7, BD=8
Minimum total cost = 4+6+7+8 = 25 (i.e. $25 000)

Understanding Prim’s from P: PQ=8, PR=5, PS=12, QR=7, QS=6, RS=4, ST=3, QT=9, RT=10.

Start at P. Available: PQ=8, PR=5, PS=12.
Step 1: Add PR=5. Tree: {P,R}.
Available from {P,R}: PQ=8, PS=12, RQ=7, RS=4, RT=10.
Step 2: Add RS=4. Tree: {P,R,S}.
Available from {P,R,S}: PQ=8, PS already reachable, RQ=7, RT=10, QS=6, ST=3.
Step 3: Add ST=3. Tree: {P,R,S,T}.
Available: PQ=8, RQ=7, QS=6, RT=10, QT=9.
Step 4: Add QS=6. Tree: {P,Q,R,S,T}. Done.

MST edges: PR=5, RS=4, ST=3, QS=6 Total weight = 18

Understanding How to identify a cycle in Kruskal’s algorithm.

In Kruskal’s algorithm, an edge creates a cycle if and only if both endpoints are already connected in the current spanning tree (i.e., they are in the same component).

How to detect: keep track of which vertices are connected to each other (as components or sets). Before adding an edge AB, check: are A and B already in the same component? If yes → skip (would create cycle). If no → add the edge (merges two components).

Example with 5 vertices and edges 1–7:
Add edge weight 1: connects two vertices (no cycle). Add 2: no cycle. Add 3: no cycle. Add 4: if this edge connects two already-connected vertices, skip it. Add next edge (5, 6, or 7) that doesn’t create a cycle until you have n−1 = 4 edges.

Understanding Pipe network: 1–2=120, 1–3=80, 2–3=60, 2–4=90, 3–4=50, 3–5=110, 4–5=40, 4–6=70, 5–6=30.

Sorted edges: 5–6=30, 4–5=40, 3–4=50, 2–3=60, 4–6=70, 1–3=80, 2–4=90, 3–5=110, 1–2=120

Add 5–6=30: {5,6} ✓
Add 4–5=40: {4,5,6} ✓
Add 3–4=50: {3,4,5,6} ✓
Add 2–3=60: {2,3,4,5,6} ✓
Add 4–6=70: both 4 and 6 already in same component → CYCLE, skip.
Add 1–3=80: {1,2,3,4,5,6} — all 6 connected. STOP (5 edges).

MST edges: 5–6=30, 4–5=40, 3–4=50, 2–3=60, 1–3=80
Minimum total pipe length = 30+40+50+60+80 = 260 metres

Problem Solving Road network 7 cities: AB=15, AC=10, AD=20, BC=8, BD=12, BE=18, CD=6, CE=14, DE=9, DF=22, EF=11, EG=16, FG=7.

(a) Kruskal’s algorithm:
Sorted: CD=6, FG=7, BC=8, DE=9, AC=10, EF=11, BD=12, CE=14, AB=15, EG=16, BE=18, AD=20, DF=22

Add CD=6: {C,D} ✓
Add FG=7: {F,G} ✓
Add BC=8: {B,C,D} ✓
Add DE=9: {B,C,D,E} ✓
Add AC=10: {A,B,C,D,E} ✓
Add EF=11: connects {A,B,C,D,E} with {F,G} → all 7 connected! STOP (6 edges).

MST: CD=6, FG=7, BC=8, DE=9, AC=10, EF=11
(b) Minimum total road length = 6+7+8+9+10+11 = 51 km

(c) Effect of EG costing twice as much per km:
EG=16 is NOT in the MST (EF=11 was chosen instead to connect {F,G} to the main component). Doubling EG’s cost to 32 does not change the MST — EG was already passed over in favour of EF=11. The MST and total weight of 51 km remain unchanged.

If instead the question asks: what if EF becomes unavailable? Then the next option to connect {F,G} to {A,B,C,D,E} is EG=16 (not doubled). New total = 51−11+16 = 56 km.

Problem Solving Two spanning trees found: weight 45 (7 edges) and weight 43 (7 edges).

(a) The tree with weight 43 is the minimum spanning tree. The MST is defined as the spanning tree with the smallest total weight. If a spanning tree of weight 43 exists, then no MST can have a higher weight — the 45-weight tree is simply a spanning tree, not the minimum.

(b) Yes, both are valid spanning trees. A spanning tree is any connected acyclic subgraph using all n vertices with exactly n−1 edges. Both trees satisfy this definition. The distinction is that one is the minimum (optimal) and one is not.

(c) Yes, a graph can have more than one MST with the same total weight.
Example: a square graph with vertices A, B, C, D and edges AB=1, BC=1, CD=1, DA=1 (all equal weights).
One MST: AB, BC, CD (total 3). Another MST: AB, BC, DA (total 3). Both are valid minimum spanning trees with the same total weight.
This happens whenever two or more edges have equal weight and could equally serve the same role in a spanning tree.