Lesson 2: Finding minimum spanning trees
A graph with two minimum spanning trees
SkillFinding minimum spanning trees
Worked example
A graph has edges 4, 3, 4, 5, 6 and 2. Find the weight of a minimum spanning tree, and decide whether the minimum spanning tree is unique.
Step 1: Order the edges
2, 3, 4, 4, 5, 6.
Step 2: Choose ST and PR
Neither makes a cycle.
Step 3: Meet the tie
and both weigh 4. Either joins to . Once one is chosen, the other would close the cycle –––.
When equal edges are interchangeable like this, each choice gives a different minimum spanning tree with the same weight.
Step 4: Finish with QS
(5) joins to . That is 4 edges for 5 vertices. (6) is not needed.
Step 5: Add the weights
Answer
The minimum weight is 14. There are two minimum spanning trees, and , so it is not unique.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Run Kruskal's method as usual.
At a tie, check whether choosing one of the equal edges rules out the other. If so, each choice gives a minimum spanning tree.
Watch out for
Choosing both and , which forms a cycle.
Thinking that two different trees must have different weights.