# Spanning trees and minimum spanning tree algorithms

> IB Mathematics AI HL · IB AI HL
> Source: https://www.owlsprep.com/study/ib-math-ai-hl-u5-spanning-trees-and-minimum-spanning/

This module introduces spanning trees and the two standard algorithms for finding minimum spanning trees (MSTs) used in IB AI HL. You will learn how to apply both Kruskal's and Prim's algorithms to solve network optimization problems.

**Prerequisites:** [Basic graph terminology and weighted graphs](https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-terminology-weighted-graphs/)

## Learning objectives

- Identify spanning trees for connected undirected graphs
- Apply Kruskal's algorithm to find a minimum spanning tree
- Apply Prim's algorithm to find a minimum spanning tree
- Calculate the total weight of a minimum spanning tree for optimization problems

## What is a Spanning Tree?

**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: $AB, BC, CD, DA, AC$.

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 $AB, BC, CD$.
3. Verify: all 4 vertices are included, the subgraph is connected, and there are no cycles. This is a valid spanning tree.

## Minimum Spanning Trees (MSTs)

**Minimum Spanning Tree (MST)** — 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.

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

*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(AB) = 4$, $w(AC) = 2$, $w(BC) = 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: $AC$ (weight 2) and $BC$ (weight 3).
3. Sum the weights: $2 + 3 = 5$. This is the total weight of the MST.

## Kruskal's Algorithm

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.

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

> **tip**
>
> Kruskal's algorithm is easiest to use when your graph is given as a list of edges, rather than an adjacency matrix.

**Worked example:** Use Kruskal's algorithm to find the MST total weight for a 4-vertex graph with edges: $AB(1), AC(4), BC(2), BD(5), CD(3)$.

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

## Prim's Algorithm

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.

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

> **tip**
>
> Prim's algorithm is easiest to use when your graph is given as an adjacency matrix, and it does not require explicit cycle checking.

**Worked example:** Use Prim's algorithm starting at $A$ to find the MST total weight for the same 4-vertex graph: $AB(1), AC(4), BC(2), BD(5), CD(3)$.

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

**Comparing methods**

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

## Common pitfalls

- **Wrong:** Stopping with the wrong number of edges
  - Why it fails: Forgetting that an $n$-vertex spanning tree always has exactly $n-1$ edges
  - Correct: Calculate $n-1$ at the start of the problem, stop once you have that many edges
- **Wrong:** Adding a cycle-forming edge in Kruskal's algorithm
  - Why it fails: Forgetting to check for cycles when adding the next smallest edge
  - Correct: Always confirm the new edge connects a vertex not already in your connected component
- **Wrong:** Believing starting vertex changes MST total weight in Prim's
  - Why it fails: Assuming different start points give different total weights
  - Correct: Any starting vertex will give the same total MST weight, even if edge sets differ
- **Wrong:** Confusing minimum and maximum spanning trees
  - Why it fails: Selecting largest edges instead of smallest by mistake
  - Correct: Double-check the question asks for minimum, always start with the smallest weight edges
- **Wrong:** Adding extra edges after all vertices are connected
  - Why it fails: Continuing to add edges instead of stopping early
  - Correct: Stop as soon as all vertices are connected, extra edges only add to the total weight and create cycles

## Cheatsheet

| Concept/Algorithm | Key Steps | Key Property |
| --- | --- | --- |
| Spanning Tree | Include all vertices, connected, no cycles | $n$ vertices $\rightarrow$ $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 |

## 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](https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/ib-math-ai-hl-u5-spanning-trees-and-minimum-spanning/