Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn9FM0Option · Decision Mathematics 1Algorithms on graphsKruskal's and Prim's algorithms

Algorithms on graphs · Subtopic 1 of 1

Minimum Spanning Trees

A minimum spanning tree (MST) connects every vertex with the least total weight and no cycles; it has $V-1$ edges. Kruskal adds the cheapest remaining edge unless it makes a cycle. Prim grows one tree, always adding the cheapest edge from the tree to a new vertex, and works directly on a distance matrix.

Edexcel YMA01 WDM11Edexcel 9FM0 OptionAQA 7367 Paper 3≈ 40 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Use Kruskal's algorithm, listing accepted and rejected edges.
Use Prim's algorithm on a network and on a distance matrix.
Find the weight of an MST.

Pause and think

A council must link five villages by cable. Why will the cheapest network never contain a loop?

Section 2 of 14

Core idea

Start hereCabling villages

A broadband company must connect five villages. Every link costs money, and the network just needs to connect everyone. Loops are wasted cable. The cheapest answer is a minimum spanning tree.

The big idea

An MST connects all $V$ vertices with $V-1$ edges and least total weight. Kruskal takes edges cheapest-first, skipping any that close a cycle; Prim grows a single tree from one vertex.

1. Kruskal

Network used below: $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CD=6$ , $CE=7$ , $DE=3$ .

Worked exampleKruskal's algorithm

Find an MST.

Goal: Edges and weight.
Strategy: Sort; add unless a cycle forms.

$BC(2)\ \checkmark$
Cheapest.
$AC(3)\ \checkmark,\ DE(3)\ \checkmark$
No cycles.
$AB(4)\ \times$
Would make cycle $ABC$ .
$BD(5)\ \checkmark$
Joins $\{A,B,C\}$ to $\{D,E\}$ ; now 4 edges.

Answer

BC,AC,DE,BD

; weight

13

✓ Check

V-1=4

edges ✓; connected ✓.

Why greedy works (cut property)

$\text{split vertices into two groups}$
Any division of the vertices.
$\text{cheapest edge across is in some MST}$
Swapping it for any heavier crossing edge can't increase the total.
$\text{Kruskal and Prim always pick such an edge}$
Each accepted edge is cheapest across some split.

2. Prim

Worked examplePrim's from A

Use Prim starting at $A$ .

Goal: Order of edges.
Strategy: Cheapest edge from tree to a new vertex.

$AC(3)$
From $A$ : $4$ or $3$ .
$CB(2)$
From $\{A,C\}$ .
$BD(5)$
Options: $BD5$ , $CD6$ , $CE7$ .
$DE(3)$
Last vertex.

AnswerSame tree, weight

13

✓ CheckBoth algorithms agree ✓.

Kruskal vs Prim

Drawing diagram…

Two greedy routes to the same tree.

TrickMatrix Prim Cross out the new vertex's row, label its column, choose the smallest uncrossed value in labelled columns.

Common misconceptionState rejections In Kruskal write which edges are rejected, e.g. "

AB

rejected: forms cycle

ABC

Pause and think

Could an MST contain the heaviest edge of the network?

Summary

$V-1$ edges, no cycles.
Kruskal: sort, avoid cycles.
Prim: grow from a vertex.

Spanning tree: Tree including every vertex.
Greedy algorithm: Takes the best immediate choice each step.

HistoryBorůvka. Otakar Borůvka found the first MST algorithm in 1926 to design an efficient electricity network for Moravia. Kruskal (1956) and Prim (1957) followed.

Fun factGreedy works. Kruskal and Prim are greedy: always take the best-looking step. For MSTs, greed is provably optimal, which is rare.

Section 3 of 14

Key formulae

Edges in a spanning tree

E=V-1

Kruskal

\text{sort edges; add cheapest unless it forms a cycle}

Prim

\text{add cheapest edge joining tree to a new vertex}

TrickPrim on a matrix. Cross out the row of each vertex you add, label its column, and pick the smallest uncrossed entry in all labelled columns.

Section 4 of 14

Worked examples

Example 1 · Kruskal0 / 3 steps

Find the MST of the network (weights

AB4

AC3

BC2

BD5

CD6

CE7

DE3

Example 2 · Prim from A0 / 3 steps

Use Prim from

A

on the same network.

Section 5 of 14

Explore the graph

The example network

Loading the interactive graph…

Try this

Vertices: $A(0,2)$ , $B(2,4)$ , $C(2,0)$ , $D(4,4)$ , $E(5,1)$ . Weights: $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CD=6$ , $CE=7$ , $DE=3$ .
The MST uses $BC$ , $AC$ , $DE$ , $BD$ : four edges for five vertices.

MST weight $13$ .

In the real worldCluster analysis. Delete the heaviest edges of an MST and the remaining pieces form natural clusters: used in biology to group similar genes.

Section 6 of 14

Common mistakes

IncorrectNot listing rejected edges

CorrectSay which edges are rejected and why

Kruskal marks need the order of consideration.

IncorrectPrim picking the cheapest edge anywhere

CorrectOnly edges touching the tree

Otherwise it's Kruskal.

Incorrect

V

edges

Correct

V-1

A tree on

V

vertices.

Adding the cheapest edge

Cycle detected. Rejected. Next.

Section 7 of 14

Exam tip

Exam tipTies. If two edges tie, either may be chosen; MSTs may not be unique, but the total weight is.

Section 8 of 14

Guided practice

SA-DM-MS-G011 markL1 FoundationNon-calculatorKruskal

How many edges are in a spanning tree of a network with

8

vertices?

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-MS-0013 marksL2 StandardNon-calculatorKruskal

Network edges:

AB4

AC3

BC2

BD5

CD6

CE7

DE3

. Find the weight of the minimum spanning tree.

Salam Academy Original Practice · Proposed mark scheme

SA-DM-MS-0021 markL2 StandardNon-calculatorPrim

Using Prim's algorithm from

A

on the same network, what is the weight of the first edge chosen?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-MS-0031 markL2 StandardNon-calculatorPrim

Using Prim from

A

, what is the weight of the third edge added?

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-MS-0042 marksL3 ExamNon-calculatorKruskal

In the same network, the weight of

CD

is reduced. Find the largest weight

CD

could have and still be part of some minimum spanning tree.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

MST: $V-1$ edges, no cycles.
Kruskal: cheapest overall, avoid cycles.
Prim: grow from one vertex.

Section 12 of 14

Quick quiz

Q1 · SA-DM-MS-Q011 markL1 FoundationNon-calculatorKruskal

Kruskal's algorithm rejects an edge when it

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: A level Further Mathematics 9FM0
Where: Decision 1 · Algorithms on graphs
Expected: Minimum spanning trees using Kruskal's and Prim's algorithms, including Prim on a distance matrix; Dijkstra's algorithm.
Calculator: Permitted; show enough working to earn the method marks.
Typical style: Edexcel often opens with a routine part and builds to a "show that" or "prove" part.
Open in: YMA01 · WDM11 9FM0 · Option

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: Pearson Edexcel 9FM0, First teaching 2017 (official specification).