Connect every point in a network using the least total weight, no loops, nothing wasted. It's how you'd lay the cheapest cabling, roads or pipes that still reach everywhere.
What even is this? A spanning tree connects all the vertices of a network with no cycles. The minimum spanning tree is the one with the smallest total edge weight. The whole topic is one tidy method: Kruskal's algorithm.
If you only do one thingSort the edges smallest first. Add each one if it doesn't make a loop. Stop when you have n − 1 edges. That's the minimum spanning tree.
The 10-minute version
Kruskal's, in one breath: sort edges → add if no cycle → stop at n − 1 edges.
For a network with 5 vertices, the tree has 4 edges. Pick the cheapest edges that never close a loop, and you're done. Then go do Practice Q1.
A tree connects vertices with no cycles. A spanning tree reaches every vertex in the network. For n vertices, a spanning tree always has exactly n − 1 edges. A network usually has many possible spanning trees, the minimum spanning tree (MST) is the one whose edge weights add to the smallest total.
Real use: connecting towns with the least total length of road, or computers with the least cable.
2 · Kruskal's algorithm
Kruskal's, the key ruleAlways add the smallest available edge that does NOT create a cycle
1
List the edges in order, smallest weight first.
2
Add the smallest edge, as long as it doesn't form a cycle (a loop back to a vertex already joined up that way).
3
If an edge would make a cycle, skip it and move to the next.
4
Stop once you have n − 1 edges, every vertex is now connected.
Don't confuse it with shortest path. Shortest path links two chosen points. An MST links all the points for the least total cost.
3 · Worked example
🏘️ Cabling five towns
Connect towns A, B, C, D, E with fibre. Edge weights are the cable costs (in $1000s). Find the cheapest network that reaches every town.
Edges: AB 4, AC 8, BC 3, BD 6, CD 5, CE 7, DE 2. Gold = chosen for the MST.
Edge (sorted)
Weight
Add?
D–E
2
✓ add
B–C
3
✓ add
A–B
4
✓ add
C–D
5
✓ add (4th edge → done)
B–D, C–E, A–C
6, 7, 8
not needed
MST = D–E, B–C, A–B, C–D. Total = 2 + 3 + 4 + 5 = $14,000. With 5 towns we needed exactly 4 edges.
4 · Practice questions
1. A network has 7 vertices. How many edges will its minimum spanning tree have?Tap to reveal
n − 1 = 7 − 1 = 6 edges. A spanning tree always has one fewer edge than the number of vertices.
2. Using Kruskal's, you've added edges of weight 1, 2 and 4. The next smallest is weight 5, but it joins two vertices that are already connected. What do you do?Tap to reveal
Skip it, it would form a cycle. Move on to the next smallest edge that connects a new vertex.
3. A pipe network of 4 towns has edges: P–Q 5, P–R 9, Q–R 4, Q–S 8, R–S 6. Find the MST and its total length.Tap to reveal
Sorted: Q–R 4, P–Q 5, R–S 6, Q–S 8, P–R 9. Add Q–R (4), add P–Q (5), add R–S (6), now all 4 towns connected (3 edges = n − 1). Skip the rest. MST = Q–R, P–Q, R–S, total = 4 + 5 + 6 = 15.