Exercises — Minimum Spanning Tree
Chapter 9 · Fully solved exercises on MST algorithms, cut/cycle properties, and applications
Exercise 1: Kruskal’s Algorithm Trace
Problem. Run Kruskal’s algorithm on the graph with nodes A, B, C, D, E and edges: A-B(3), A-C(5), B-C(2), B-D(4), C-E(6), D-E(1), B-E(7).
Find the MST and its total weight.
Solution
Sort edges by weight: D-E(1), B-C(2), A-B(3), B-D(4), A-C(5), C-E(6), B-E(7).
Step-by-step trace:
| Edge | Weight | Action | Components after |
|---|---|---|---|
| D-E | 1 | Add | {A}, {B}, {C}, {D,E} |
| B-C | 2 | Add | {A}, {B,C}, {D,E} |
| A-B | 3 | Add | {A,B,C}, {D,E} |
| B-D | 4 | Add | {A,B,C,D,E} — MST complete |
| A-C | 5 | Skip (cycle in {A,B,C}) | — |
| C-E | 6 | Skip (MST complete) | — |
| B-E | 7 | Skip (MST complete) | — |
MST edges: D-E(1), B-C(2), A-B(3), B-D(4). Total weight = 1 + 2 + 3 + 4 = 10.
Exercise 2: Prim’s Algorithm
Problem. Run Prim’s algorithm starting from node A on the same graph.
Solution
Prim’s algorithm grows a tree one node at a time, always picking the minimum-weight frontier edge.
| Step | Tree T | Frontier edges | Chosen |
|---|---|---|---|
| 0 | {A} | A-B(3), A-C(5) | A-B(3) |
| 1 | {A,B} | A-C(5), B-C(2), B-D(4), B-E(7) | B-C(2) |
| 2 | {A,B,C} | A-C(5 — already in T), B-D(4), B-E(7), C-E(6) | B-D(4) |
| 3 | {A,B,C,D} | B-E(7), C-E(6), D-E(1) | D-E(1) |
| 4 | {A,B,C,D,E} | — | Done |
MST edges: A-B(3), B-C(2), B-D(4), D-E(1). Total weight = 3 + 2 + 4 + 1 = 10. Same MST as Kruskal’s.
Exercise 3: Cut Property Application
Problem. Consider the cut \(S = \{A,B,C\}\) vs \(\bar{S} = \{D,E\}\) in the graph from Exercise 1. Which edges cross the cut? What does the cut property say about the MST?
Solution
An edge crosses the cut if one endpoint is in \(S\) and the other is in \(\bar{S} = \{D,E\}\).
| Edge | Endpoints | Crosses cut? |
|---|---|---|
| A-B(3) | both in S | No |
| A-C(5) | both in S | No |
| B-C(2) | both in S | No |
| B-D(4) | B ∈ S, D ∈ \(\bar{S}\) | Yes |
| B-E(7) | B ∈ S, E ∈ \(\bar{S}\) | Yes |
| C-E(6) | C ∈ S, E ∈ \(\bar{S}\) | Yes |
| D-E(1) | both in \(\bar{S}\) | No |
Crossing edges: B-D(4), B-E(7), C-E(6). Minimum-weight crossing edge: B-D(4).
Cut Property: The minimum-weight edge crossing any cut must belong to every MST (when edge weights are distinct).
Therefore B-D(4) is in every MST of this graph. This is confirmed: B-D(4) is indeed in our MST found in Exercises 1 and 2.
Exercise 4: MST Uniqueness
Problem. (a) Is the MST always unique? When is it unique? (b) Given the triangle graph A-B(1), B-C(1), A-C(1), how many MSTs exist? (c) Modify one edge weight so the MST becomes unique.
Solution
(a) Uniqueness condition.
The MST is unique if and only if all edge weights are distinct. If some edges share the same weight, there may be multiple minimum spanning trees: by the cycle property, any maximum-weight edge in a cycle can be removed, but if the maximum weight is shared by two edges in the cycle, either can be removed, yielding two different MSTs.
(b) All-equal triangle: A-B(1), B-C(1), A-C(1).
Any 2-edge spanning tree of a 3-node graph is a spanning tree. All 2-edge subsets have equal total weight \(1+1=2\). The three spanning trees are:
- MST 1: {A-B(1), B-C(1)}
- MST 2: {A-B(1), A-C(1)}
- MST 3: {B-C(1), A-C(1)}
There are 3 MSTs, each of weight 2.
(c) Break the tie. Change A-C to weight 2: edges A-B(1), B-C(1), A-C(2).
Now the only MST is {A-B(1), B-C(1)} with total weight 2. The edge A-C(2) is the unique maximum in the cycle A-B-C-A, so it is excluded by the cycle property.
Exercise 5: MST Application — Network Design
Problem. A company wants to connect 5 warehouses with cables. Construction costs: W1-W2: 8, W1-W3: 5, W1-W4: 10, W2-W3: 4, W2-W5: 6, W3-W4: 7, W3-W5: 3, W4-W5: 9.
Find the minimum total cost to connect all warehouses.
Solution
This is exactly an MST problem: the graph’s MST gives the cheapest connected cable network.
Apply Kruskal’s algorithm:
| Edge | Cost | Action | Components after |
|---|---|---|---|
| W3-W5 | 3 | Add | {W3,W5}, {W1}, {W2}, {W4} |
| W2-W3 | 4 | Add | {W2,W3,W5}, {W1}, {W4} |
| W1-W3 | 5 | Add | {W1,W2,W3,W5}, {W4} |
| W2-W5 | 6 | Skip | cycle in {W1,W2,W3,W5} |
| W3-W4 | 7 | Add | {W1,W2,W3,W4,W5} — done |
| W1-W2 | 8 | Skip | MST complete |
| W4-W5 | 9 | Skip | MST complete |
| W1-W4 | 10 | Skip | MST complete |
MST: W3-W5(3), W2-W3(4), W1-W3(5), W3-W4(7). Minimum total cost = 3 + 4 + 5 + 7 = 19.