Spanning trees and minimum spanning tree algorithms

IB Mathematics AI HL· 45 min read

1. What is a Spanning Tree?★★☆☆☆⏱ 10 min

📘 Definition

Spanning Tree

A connected, acyclic subgraph of a connected undirected graph that includes every vertex from the original graph. For a graph with $n$ vertices, any spanning tree will always have exactly $n - 1$ edges.

Example:

A spanning tree for a 4-vertex graph will always have exactly 3 edges.

Most connected graphs have multiple possible spanning trees. Spanning trees simplify the original graph by removing cycles while retaining connectivity between all vertices, which makes them useful for network design problems.

📐 Worked Example

Draw one valid spanning tree for a connected graph with 4 vertices $A, B, C, D$ and edges: $A B, B C, C D, D A, A C$ .

1
Count the number of vertices: $n = 4$ , so the spanning tree needs $n - 1 = 3$ edges.
2
Select 3 edges that connect all vertices with no cycles. One valid selection is edges $A B, B C, C D$ .
3
Verify: all 4 vertices are included, the subgraph is connected, and there are no cycles. This is a valid spanning tree.

2. Minimum Spanning Trees (MSTs)★★☆☆☆⏱ 10 min

📘 Definition

Minimum Spanning Tree (MST)

Total weight: $W = \sum_{e \in T} w (e)$ where $T$ is the spanning tree

For a weighted connected undirected graph, an MST is a spanning tree where the sum of edge weights is smaller than or equal to the total weight of any other spanning tree for the graph.

Example:

An MST connecting 3 cities with edge weights 2, 3, 5 has a total weight of 5, the sum of the two smallest connecting edges.

MSTs are used for real-world problems like finding the lowest-cost pipeline network connecting multiple towns, or designing a minimum-cost fiber-optic network. Any weighted connected graph has at least one MST; if all edge weights are distinct, there is exactly one MST.

📐 Worked Example

A graph has 3 vertices $A, B, C$ with edge weights $w (A B) = 4$ , $w (A C) = 2$ , $w (B C) = 3$ . Find the total weight of the MST.

1
For $n = 3$ vertices, the MST needs $3 - 1 = 2$ edges.
2
Select the two smallest edges that connect all vertices without cycles: $A C$ (weight 2) and $B C$ (weight 3).
3
Sum the weights: $2 + 3 = 5$ . This is the total weight of the MST.

3. Kruskal's Algorithm★★★☆☆⏱ 15 min

Kruskal's algorithm is a greedy algorithm that builds the MST by adding edges in order of increasing weight, skipping any edge that creates a cycle.

List all edges in order of increasing weight
Start with an empty set of edges for the MST
Add the next smallest edge if it does not create a cycle with existing edges
Repeat until you have $n - 1$ edges (all vertices connected)

📐 Worked Example

Use Kruskal's algorithm to find the MST total weight for a 4-vertex graph with edges: $A B (1), A C (4), B C (2), B D (5), C D (3)$ .

1
Sort edges by weight: $A B (1), B C (2), C D (3), A C (4), B D (5)$ .
2
Add $A B$ : no cycle, current edges: ${A B}$ , connected vertices: ${A, B}$ .
3
Add $B C$ : no cycle, current edges: ${A B, B C}$ , connected vertices: ${A, B, C}$ .
4
Add $C D$ : no cycle, connects D, current edges: ${A B, B C, C D}$ (3 edges for 4 vertices, done).
5
Total weight: $1 + 2 + 3 = 6$ .

4. Prim's Algorithm★★★☆☆⏱ 15 min

Prim's algorithm is also a greedy algorithm, but it builds the MST by starting at a single vertex and repeatedly adding the smallest edge that connects a new vertex to the existing tree.

Choose any starting vertex and add it to the MST set
Find the smallest weight edge connecting a vertex inside the MST set to a vertex outside
Add this edge and the new vertex to the MST set
Repeat until all vertices are added to the MST set

📐 Worked Example

Use Prim's algorithm starting at $A$ to find the MST total weight for the same 4-vertex graph: $A B (1), A C (4), B C (2), B D (5), C D (3)$ .

1
Start with MST set: ${A}$ , no edges added.
2
Smallest edge from $A$ to outside is $A B (1)$ . Add $A B$ and $B$ , MST set: ${A, B}$ .
3
Smallest edge from ${A, B}$ to outside is $B C (2)$ . Add $B C$ and $C$ , MST set: ${A, B, C}$ .
4
Smallest edge from ${A, B, C}$ to outside is $C D (3)$ . Add $C D$ and $D$ , all vertices included.
5
Total weight: $1 + 2 + 3 = 6$ , same result as Kruskal's algorithm.

Methods compared

Both algorithms produce the correct MST, but they are suited to different input formats:

Kruskal's

Sorts edges first, adds edges avoiding cycles

+ Pros: Easy for edge lists, sparse graphs

− Cons: Requires cycle checking each step

Prim's

Builds from a starting vertex, adds nearest vertex

+ Pros: No explicit cycle checking, good for adjacency matrices

− Cons: Less intuitive for beginners with arbitrary start points

5. Common Pitfalls

Wrong move:

Stopping with the wrong number of edges

Why:

Forgetting that an $n$ -vertex spanning tree always has exactly $n - 1$ edges

Correct move:

Calculate $n - 1$ at the start of the problem, stop once you have that many edges

Wrong move:

Adding a cycle-forming edge in Kruskal's algorithm

Why:

Forgetting to check for cycles when adding the next smallest edge

Correct move:

Always confirm the new edge connects a vertex not already in your connected component

Wrong move:

Believing starting vertex changes MST total weight in Prim's

Why:

Assuming different start points give different total weights

Correct move:

Any starting vertex will give the same total MST weight, even if edge sets differ

Wrong move:

Confusing minimum and maximum spanning trees

Why:

Selecting largest edges instead of smallest by mistake

Correct move:

Double-check the question asks for minimum, always start with the smallest weight edges

Wrong move:

Adding extra edges after all vertices are connected

Why:

Continuing to add edges instead of stopping early

Correct move:

Stop as soon as all vertices are connected, extra edges only add to the total weight and create cycles

6. Quick Reference Cheatsheet

Concept/Algorithm	Key Steps	Key Property
Spanning Tree	Include all vertices, connected, no cycles	$n$ vertices $\to$ $n - 1$ edges
Minimum Spanning Tree	Spanning tree with minimum total edge weight	At least one MST exists for all connected weighted graphs
Kruskal's	Sort edges by weight, add smallest, avoid cycles, stop at $n - 1$ edges	Best for edge lists / sparse graphs
Prim's	Start at any vertex, add smallest edge to new vertex, repeat until all included	Best for adjacency matrices / dense graphs, no cycle check needed

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2025 · Paper 1
MST optimization problem
2023 · Paper 2
Apply Prim's algorithm
2021 · Paper 1
Compare Kruskal and Prim methods

Going deeper

syllabusIB AI HL Topic 5 SyllabusOfficial syllabus reference

What's Next

Spanning trees and MST algorithms are core concepts for graph theory optimization in IB AI HL. They form the foundation for more advanced network problems like shortest path finding and maximum flow, which are also commonly tested in exams. MST problems often appear in both Paper 1 and Paper 2, usually paired with real-world contexts like transport network design or communications infrastructure. Practicing both algorithms until you can apply them confidently will help you earn full marks on these common exam questions.

→Graph theory applications: CPP and TSP