Minimum Spanning Trees

Imagine wiring up a set of houses with broadband, or laying water pipes between towns: you must connect every site, but you want to use the least total cable. Strip away the context and the problem is purely abstract — find, inside a network, a set of edges that keeps everything connected at minimum total weight. The answer is always a tree (any cycle wastes an edge), and a minimum-weight one is a minimum spanning tree (MST). This lesson develops two classic greedy algorithms — Kruskal's and Prim's — that build an MST efficiently and provably, and shows why two very different strategies reach the same minimum weight.

---

1. Where this sits in AQA 7367

This is a flagship optimisation topic of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). Running an algorithm correctly is AO1; choosing and justifying the method, and arguing why the greedy choice is optimal, is AO2/AO3. The matrix form of Prim's algorithm is the AQA house style and the form most often examined, so master it specifically.

---

2. Core theory: spanning trees

Term	Definition
Spanning subgraph	A subgraph that includes all vertices of $G$G
Spanning tree	A spanning subgraph that is connected and acyclic (a tree)
Minimum spanning tree (MST)	A spanning tree of minimum total edge weight

A spanning tree of a connected graph on $n$n vertices has exactly $n - 1$n−1 edges (the defining tree property). The total weight of a tree $T$T is

$w(T) = \sum_{e \in T} w(e),$w(T)=∑e∈T​w(e),

and an MST minimises this over all spanning trees. Greedy algorithms work here because of the cut property: for any partition of the vertices into two non-empty sets, the lightest edge crossing the cut belongs to some MST. Both algorithms below repeatedly add a lightest crossing edge, which is why they are correct.

---

3. Kruskal's algorithm (edge-focused) with M1/A1 mark scheme

Strategy. Consider edges in increasing weight order; add an edge unless it would create a cycle; stop after $n - 1$n−1 edges.

Procedure

1. Sort all edges by weight, ascending.
2. Start with all vertices and no edges.
3. Take the next cheapest edge. Reject it if it forms a cycle with edges already chosen; otherwise add it.
4. Stop when $n - 1$n−1 edges have been chosen.

Worked Example 3.1

Graph on A, B, C, D, E with the edges below. Find an MST by Kruskal's algorithm.

Edge	AB	AC	AD	BC	BD	CD	CE	DE
Weight	3	5	8	4	6	2	7	1

Sorted: DE(1), CD(2), AB(3), BC(4), AC(5), BD(6), CE(7), AD(8). (M1 for a fully correct sort.)

Step	Edge	Decision	Reason
1	DE (1)	add	no cycle
2	CD (2)	add	no cycle
3	AB (3)	add	no cycle
4	BC (4)	add	joins $\{A,B\}${A,B} to $\{C,D,E\}${C,D,E}, no cycle
5	AC (5)	reject	would close cycle $A\!-\!B\!-\!C\!-\!A$A−B−C−A

After $4 = n - 1$4=n−1 edges we stop. MST edges: DE, CD, AB, BC, with weight

$w(T) = 1 + 2 + 3 + 4 = 10.$w(T)=1+2+3+4=10.

(A1 for the correct set of edges; A1 for the total $10$10.)

graph LR
  A((A)) ---|3| B((B))
  B ---|4| C((C))
  C ---|2| D((D))
  D ---|1| E((E))

Exam tip. Always show the sorted list and name the cycle you would create when you reject an edge — that is where the AO2 reasoning mark lives.

---

4. Prim's algorithm — network (graphical) form

Strategy. Grow a single tree outward from a starting vertex, each step adding the cheapest edge joining a tree-vertex to a non-tree vertex.

Procedure

1. Pick any start vertex; mark it "in tree".
2. Among all edges from a tree-vertex to a non-tree vertex, choose the cheapest.
3. Add that edge and its new vertex to the tree.
4. Repeat until all $n$n vertices are in the tree ($n - 1$n−1 additions).

Worked Example 4.1 (same graph, start at A)

Step	Tree so far	Candidate edges (tree → non-tree)	Add
1	$\{A\}${A}	AB(3), AC(5), AD(8)	AB(3)
2	$\{A,B\}${A,B}	BC(4), AC(5), BD(6), AD(8)	BC(4)
3	$\{A,B,C\}${A,B,C}	CD(2), AC(5), BD(6), CE(7), AD(8)	CD(2)
4	$\{A,B,C,D\}${A,B,C,D}	DE(1), CE(7), BD(6), AD(8)	DE(1)

MST edges: AB, BC, CD, DE, total $3 + 4 + 2 + 1 = 10$3+4+2+1=10 — the same minimum weight as Kruskal's. (The order of selection differs; the resulting tree and its weight do not.)

---

5. Prim's algorithm — matrix form (the AQA house method) with M1/A1

When the network is given as a distance matrix, Prim's runs as a tidy row/column procedure.

Procedure

1. Choose a start vertex; cross out its row and circle its column.
2. Among all circled columns, find the smallest uncrossed entry.
3. That entry's row is the next vertex: add the edge, cross out that row, circle that column, and record the order of selection.
4. Repeat until every column is circled.

Worked Example 5.1 (start at A)

	A	B	C	D	E
A	–	3	5	8	$\infty$∞
B	3	–	4	6	$\infty$∞
C	5	4	–	2	7
D	8	6	2	–	1
E	$\infty$∞	$\infty$∞	7	1	–

• Start A → cross row A, circle column A. (M1 for correct start.)
• Smallest in circled cols $\{A\}${A}: $3$3 in row B (edge AB). Add B; circle col B, cross row B.
• Smallest in $\{A,B\}${A,B}: $4$4 in row C (edge BC). Add C; circle col C, cross row C.
• Smallest in $\{A,B,C\}${A,B,C}: $2$2 in row D (edge CD). Add D; circle col D, cross row D.
• Smallest in $\{A,B,C,D\}${A,B,C,D}: $1$1 in row E (edge DE). Add E.

Selection order: A, B, C, D, E. MST edges: AB(3), BC(4), CD(2), DE(1), total $= 10$=10. (A1 edges; A1 total.)

Exam tip. Record the order vertices join and the edge used at each step — examiners award method marks for a clearly annotated crossing/circling, even if a single arithmetic comparison slips.

---

6. A second network: Prim and Kruskal agree

Graph on A, B, C, D, E, F with edges AB(4), AF(2), BC(6), BF(5), CD(3), CF(1), DE(2), DF(4), EF(7).

Kruskal (sorted): CF(1), AF(2), DE(2), CD(3), AB(4), DF(4), BF(5), BC(6), EF(7).

Edge	CF(1)	AF(2)	DE(2)	CD(3)	AB(4)	DF(4)
Decision	add	add	add	add	add	reject (cycle C–D–F–C)

After $5$5 edges we stop. MST = CF, AF, DE, CD, AB with weight $1 + 2 + 2 + 3 + 4 = 12$1+2+2+3+4=12.

Prim (start A): add A→F(2), F→C(1), C→D(3), D→E(2), A→B(4). Same five edges, total $12$12. Both methods give $w(T) = 12$w(T)=12, confirming the MST weight is independent of the algorithm.

graph LR
  A((A)) ---|2| F((F))
  F ---|1| C((C))
  C ---|3| D((D))
  D ---|2| E((E))
  A ---|4| B((B))

Observe how Kruskal and Prim build the same tree by different routes: Kruskal picks edges purely by global cheapness (CF, AF, DE, CD, AB), so it can grow several tree-fragments at once and merge them, whereas Prim keeps a single connected fragment that swallows one new vertex at a time. The rejected edge DF(4) is instructive — at the moment it is considered, C, D and F are already linked through CF and CD, so DF would close the triangle $C\!-\!D\!-\!F\!-\!C$C−D−F−C; by the cycle property the heaviest edge on any cycle is safe to discard, and DF(4) is indeed the heaviest of $\{CF(1), CD(3), DF(4)\}${CF(1),CD(3),DF(4)}.

MST is not the shortest-path tree

A frequent and costly confusion is to treat the MST as if it gave shortest routes. Consider a triangle on $\{X, Y, Z\}${X,Y,Z} with $XY = 1,\ YZ = 1,\ XZ = 3$XY=1, YZ=1, XZ=3. The MST keeps the two cheap edges $XY$XY and $YZ$YZ (weight $2$2) and drops $XZ$XZ. But the shortest path from X to Z within the MST is $X\!-\!Y\!-\!Z$X−Y−Z of length $2$2 — which happens to beat the direct edge $3$3 here, yet in general the MST path between two vertices can be far longer than their true shortest path. The MST minimises the total wiring cost across the whole network; Dijkstra (Lesson 4) minimises the cost of one specific route. They answer different questions and usually give different trees.

---

7. Specimen-style exam question

(Specimen-style — not from any past paper.)

The table is the distance matrix of a network connecting five pumping stations P, Q, R, S, T (weights in km; "–" means no direct pipe).

	P	Q	R	S	T
P	–	6	1	5	–
Q	6	–	4	–	3
R	1	4	–	2	7
S	5	–	2	–	8
T	–	3	7	8	–

(a) Use Prim's algorithm starting from P to find a minimum spanning tree. List the edges in the order you select them. [4] (b) State the total length of pipe required. [1]

Model solution. (a) Start P (circle col P, cross row P). Smallest in $\{P\}${P}: $1$1 → R (PR). Smallest in $\{P,R\}${P,R}: $2$2 → S (RS). Smallest in $\{P,R,S\}${P,R,S}: $4$4 → Q (RQ). Smallest in $\{P,R,S,Q\}${P,R,S,Q}: $3$3 → T (QT). Edges in order: PR(1), RS(2), RQ(4), QT(3). [M1 method, A1 A1 A1 for correct successive edges] (b) Total $= 1 + 2 + 4 + 3 = 10$=1+2+4+3=10 km. [B1]

---

Tied weights and non-unique MSTs

When edge weights are all distinct the MST is unique, but ties can produce several MSTs of equal weight. Consider a square $A\!-\!B\!-\!C\!-\!D\!-\!A$A−B−C−D−A with all four sides of weight $1$1 and one diagonal $AC$AC of weight $2$2. An MST needs $3$3 edges; any three of the four unit sides form a spanning tree of weight $3$3, so there are $4$4 distinct MSTs (drop any one side), all avoiding the heavier diagonal. Kruskal's algorithm, faced with the tie, may pick the equal-weight edges in any order; whichever it chooses, the total weight is the same ($3$3). In an exam, if asked "is the MST unique?", check for repeated weights: equal weights crossing the same cut are the signature of multiple optima. State the total weight (which is always well-defined) and, if relevant, note that the tree is not unique.

Where MSTs are used