Minimum Spanning Tree (AI HL)
A minimum spanning tree connects every vertex in a weighted graph as cheaply as possible, using no more edges than it needs and never forming a cycle. This page covers how Kruskal's and Prim's algorithms build one, with worked examples and the mistakes that lose marks. It's part of the broader Graph Theory topic.
19 questions on this sub-topic.
Building a minimum spanning tree
Covered under IB syllabus reference AHL3.16: minimum spanning tree algorithms (Kruskal's and Prim's), part of the wider unit on walks, trails, paths, circuits and cycles.
Tree edge count
A spanning tree on \(n\) vertices always has \(n-1\) edges.
Not in the formula booklet - it's a direct consequence of a tree having no cycles. Use it to check your working: if you've kept more or fewer than \(n-1\) edges, you've made an error.
Kruskal's vs Prim's
Kruskal's: sort all edges by weight, add the cheapest one at a time, skipping any that would create a cycle.
Prim's: start at one vertex and repeatedly add the cheapest edge connecting the growing tree to a new vertex.
Not in the formula booklet - these are algorithms you apply by hand, showing your working at each step. Both always reach the same minimum total weight.
Want the full syllabus wording, the Chinese postman problem, and the travelling salesman algorithms? See Graph Theory.
Worked examples
Using Kruskal's algorithm on the weighted graph, find the minimum spanning tree and its total weight.
Worked solution
Sorted: AC 3, CD 4, AB 5, BD 6, AD 7. Add AC, CD, AB (no cycle, 4 vertices connected). M1
MST = {AC, CD, AB}. A1
Total \(= 3 + 4 + 5 = 12.\) A1
Apply Prim's algorithm starting at vertex A to the same network, listing the order edges are added.
Worked solution
Start A. AC(3), then CD(4), then AB(5) (vs BD 6). M1
Order: AC, CD, AB. A1
Total \(= 12\) (same MST as Kruskal). A1
Common mistakes
- Confusing a minimum spanning tree with a shortest path. An MST minimises the total cost to connect every vertex - it does not give the shortest route between two particular vertices, which is a different problem (solved with Dijkstra's algorithm).
- Adding an edge in Kruskal's algorithm without checking for a cycle. Sorting by weight is only half the method - each candidate edge must also be rejected if both its endpoints are already connected through edges you've kept.
- Treating the MST as if it must visit every vertex and return to the start. That's the travelling salesman problem, a different task. A spanning tree is not a cycle, and it has no requirement to close back on itself.
Ready to practise properly?
20 minimum spanning tree questions, marked instantly like the real exam.
Quick answers
How many edges does a minimum spanning tree have?
A spanning tree on \(n\) vertices always has exactly \(n-1\) edges - enough to connect every vertex with no cycles, and no more.
Do Kruskal's and Prim's algorithms always give the same minimum spanning tree?
They always produce a tree of the same minimum total weight, but if two or more edges tie in weight the two methods can pick a different set of edges to reach it.