What are the key types of algorithms used on graphs in Decision Mathematics 1?

In Decision Mathematics 1, particularly for the Edexcel International A Levels, the key types of algorithms used on graphs include Dijkstra's algorithm for finding the shortest path, Prim's and Kruskal's algorithms for finding the minimum spanning tree, and the algorithm for determining Eulerian and Hamiltonian paths. These algorithms are fundamental for solving problems related to network optimization and pathfinding.

How does Dijkstra's algorithm work in finding the shortest path on a graph?

Dijkstra's algorithm is used to find the shortest path from a starting vertex to all other vertices in a weighted graph. It works by iteratively selecting the vertex with the smallest tentative distance, updating the distances of its adjacent vertices, and marking it as 'visited'. This process continues until all vertices have been visited, ensuring the shortest path is found. This algorithm is crucial for network routing and is a key topic in the Edexcel International A Levels Decision Mathematics 1 curriculum.

What is the difference between Prim's and Kruskal's algorithms for minimum spanning trees?

Prim's and Kruskal's algorithms are both used to find the minimum spanning tree of a graph, but they operate differently. Prim's algorithm starts with a single vertex and grows the spanning tree by adding the smallest edge that connects the tree to a new vertex. In contrast, Kruskal's algorithm sorts all the edges by weight and adds them one by one to the spanning tree, ensuring no cycles are formed. Understanding these differences is essential for students studying Decision Mathematics 1 under the Edexcel International A Levels.

What is an Eulerian path, and how can it be identified in a graph?

An Eulerian path is a trail in a graph that visits every edge exactly once. A graph has an Eulerian path if it is connected and has exactly zero or two vertices of odd degree. If there are no vertices of odd degree, the path is also a circuit, known as an Eulerian circuit. Identifying Eulerian paths is a key concept in graph theory, which is part of the Decision Mathematics 1 syllabus for Edexcel International A Levels.

How can Hamiltonian paths be distinguished from Eulerian paths in graph algorithms?

Hamiltonian paths differ from Eulerian paths in that they visit each vertex exactly once, rather than each edge. Determining the existence of a Hamiltonian path is more complex and does not have a straightforward algorithm like Eulerian paths. However, understanding the properties and applications of Hamiltonian paths is important for students studying graph algorithms in Decision Mathematics 1 for the Edexcel International A Levels.

Why is "Listing only the accepted edges in Kruskal's, not the rejected ones" a common mistake in Algorithms on graphs?

Why it happens: Rejected edges feel irrelevant. How to avoid it: Edexcel mark schemes split marks between acceptance and rejection. ALWAYS write 'Accept AB', 'Accept BC', 'AC rejected — cycle A-B-C', etc. Cycle justification is essential. Source: WDM01/01 Examiner Reports — flagged every session

Why is "Doing a cycle check during Prim's algorithm" a common mistake in Algorithms on graphs?

Why it happens: Confusing Prim with Kruskal. How to avoid it: Prim NEVER needs a cycle check — by construction it adds an edge to a vertex NOT yet in the tree. The constraint is 'unvisited vertex', not 'no cycle'.

Why is "Crossing out COLUMNS instead of rows in Prim's matrix form" a common mistake in Algorithms on graphs?

Why it happens: Mixing up Edexcel's convention. How to avoid it: Edexcel convention: LABEL columns of visited vertices, CROSS OUT rows of visited vertices. Then scan labelled columns for the smallest entry in an unlabelled (un-crossed) row.

Why is "Assuming the MST is unique" a common mistake in Algorithms on graphs?

Why it happens: Algorithms give an answer, so 'the' MST. How to avoid it: If two edges tie in weight, there can be MULTIPLE MSTs (all with the same total weight). Choose either by the question's tie-breaking rule (usually alphabetical), but state if a tie occurs.

Why is "Counting a loop as contributing $1$ to the degree" a common mistake in Algorithms on graphs?

Why it happens: Treating a loop like an ordinary edge. How to avoid it: A loop contributes 2 to the degree of its vertex (both ends are at the same vertex). Most D1 questions use simple graphs (no loops) — but the rule matters for handshaking checks.

Why is "Not verifying $\sum \deg = 2E$ as a sanity check" a common mistake in Algorithms on graphs?

Why it happens: Just calculating degrees and moving on. How to avoid it: A 30-second handshake check catches degree-counting errors. If is odd, you have an error. Make this routine.

Edexcel International A Levels Mathematics (XMA01-YMA01)

Algorithms on graphs

0% Complete

Detailed Study Notes

Detailed notes on Decision Mathematics 1 for Edexcel International A Levels Mathematics, covering key concepts, explanations, examples, and exam-focused revision points.

Algorithms on Graphs Study Notes — Edexcel IAL Mathematics D1 (WDM01/01, 2018 spec — 2026 onwards)

Vocabulary: vertex, edge, degree, simple, weighted, directed, connected, tree, cycle, planar. Handshaking lemma: $\sum \deg(v) = 2E$ . Euler's planar formula: $V - E + F = 2$ (NOT in the IAL booklet). Two MST algorithms: KRUSKAL'S — sort edges by weight and add the next non-cycle-forming edge — and PRIM'S — start at any vertex and add the shortest edge to an unconnected vertex. Prim's matrix form: label columns of visited vertices, cross out their rows, scan labelled columns for the smallest unlabelled-row entry.

At a glance

Vertex (node) + edge (arc) = graph.
Degree of a vertex = number of incident edges (loops count twice).
Handshaking: $\sum \deg(v) = 2E$ .
Euler (planar): $V - E + F = 2$ (NOT in the IAL booklet).
Tree = connected, no cycles. Spanning tree = tree covering all vertices.
MST = spanning tree of minimum total weight; $n-1$ edges.
Kruskal: sort edges; accept if no cycle; stop at $n-1$ accepted.
Prim: start anywhere; add shortest edge to an unvisited vertex.
Prim matrix: label columns of visited vertices, cross out rows, scan.

What you’ll learn

Mapped to the Pearson Edexcel International A Levels XMA01-YMA01 syllabus (2026 onwards).

D1 2.1 — Use graph-theoretic vocabulary correctly (vertex, edge, degree, simple, connected, tree, planar).
D1 2.2 — Apply Kruskal's algorithm to find a minimum spanning tree.
D1 2.3 — Apply Prim's algorithm on a graph and on a distance matrix.
D1 2.4 — Compare and contrast Kruskal's and Prim's algorithms.

Graph vocabulary

Vertex, edge, degree, simple, connected, tree, cycle, planar.

Graph $G = (V, E)$ : a set of vertices (nodes) $V$ and a set of edges (arcs) $E$ that join pairs of vertices.

Degree $\deg(v)$ of vertex $v$ = number of edges incident with $v$ . A loop (edge from $v$ to itself) contributes $2$ to $\deg(v)$ .

Handshaking lemma. The sum of all degrees equals twice the number of edges: $\sum_{v \in V} \deg(v) = 2|E|.$ Consequence: the number of odd-degree vertices is always EVEN.

Simple graph. No loops; at most one edge between each pair of vertices.

Multigraph. Multiple edges between the same pair are allowed.

Weighted graph. Each edge has a numerical weight (distance, cost, time).

Directed graph (digraph). Each edge has a direction (arrow). $\deg^{+}(v)$ = out-degree; $\deg^{-}(v)$ = in-degree.

Walk. A sequence of edges where each edge starts at the vertex the previous one ended.

Path. A walk with no repeated vertices (and so no repeated edges).

Cycle. A walk that returns to its starting vertex with no other repeats.

Connected graph. There is a path between every pair of vertices.

Tree. A connected graph with no cycles. Equivalently: a connected graph with exactly $n - 1$ edges on $n$ vertices.

Spanning tree. A tree that includes every vertex of $G$ .

Planar graph. A graph that can be drawn in the plane without edge crossings. For a CONNECTED planar graph, $V - E + F = 2$ where $F$ is the number of faces, including the outer unbounded face.

Bipartite graph. Vertices split into two sets $A, B$ with edges only between $A$ and $B$ . (Less central in D1 but defined in the spec.)

Kruskal's / Prim's algorithm finds the minimum spanning tree — the cheapest tree linking every vertex.

$\sum \deg(v) = 2|E|$ (handshaking).
Loop contributes $2$ to degree.
Tree: connected, $n - 1$ edges, no cycles.
Planar: $V - E + F = 2$ .

Kruskal's algorithm

Sort edges by weight, add the next one that doesn't form a cycle.

Kruskal's algorithm finds a Minimum Spanning Tree (MST) of a connected weighted graph.

Procedure.

List all edges in INCREASING order of weight (break ties however you like — write the order you choose).
Consider each edge in turn.
If it does NOT form a cycle with the edges already accepted, ACCEPT it.
Otherwise REJECT it (write 'cycle').
Stop when $n - 1$ edges have been accepted.

Worked example. Graph with $6$ vertices and edges:

$AB=3, AC=5, AD=6, BC=2, BD=4, CD=7, CE=8, DE=3, DF=4, EF=5$ .

Sorted: $BC(2), AB(3), DE(3), BD(4), DF(4), AC(5), EF(5), AD(6), CD(7), CE(8)$ .

Edge	Weight	Action	Reason
$BC$	2	accept	first edge
$AB$	3	accept	no cycle
$DE$	3	accept	no cycle (separate component)
$BD$	4	accept	links $\{A,B,C\}$ with $\{D,E\}$
$DF$	4	accept	adds $F$
$AC$	5	reject	cycle $A$ - $B$ - $C$ - $A$
$EF$	5	reject	cycle $D$ - $E$ - $F$ - $D$
...	...	(rejected)

Stop after $5 = n - 1$ accepted edges. Total $= 2 + 3 + 3 + 4 + 4 = 16$ .

Cycle check. Edge $XY$ forms a cycle iff $X$ and $Y$ are already in the same connected component of the partial tree. Visually: if you can already get from $X$ to $Y$ using accepted edges, adding $XY$ closes a cycle.

Why it works. A 'greedy' choice — the smallest weight edge that doesn't create a cycle — is globally optimal because of the matroid structure of spanning trees.

Sort edges increasing.
Accept if no cycle; reject (and state cycle) if cycle.
Stop at $n - 1$ accepted edges.
Show ALL rejections with the cycle reason.

Prim's algorithm

Start anywhere; add the shortest edge to an unconnected vertex.

Prim's algorithm also finds an MST.

Procedure.

Pick any starting vertex; call this the initial tree.
From the current tree, find the SHORTEST EDGE that connects a tree vertex to a vertex NOT yet in the tree.
Add that edge (and the new vertex) to the tree.
Repeat until all $n$ vertices are in the tree.

Key feature. Prim's never needs a cycle check — by construction, every added vertex is new.

Worked example. Same graph as before, start at $A$ .

Step	Tree	Crossing edges	Add
1	$\{A\}$	$AB=3, AC=5, AD=6$	$AB$ (3); tree $\{A,B\}$
2	$\{A,B\}$	$BC=2, AC=5, BD=4, AD=6$	$BC$ (2); tree $\{A,B,C\}$
3	$\{A,B,C\}$	$BD=4, AD=6, CD=7, CE=8$	$BD$ (4); tree $\{A,B,C,D\}$
4	$\{A,B,C,D\}$	$DE=3, DF=4, CE=8$	$DE$ (3); tree $\{A,B,C,D,E\}$
5	$\{A,B,C,D,E\}$	$DF=4, EF=5$	$DF$ (4); tree $\{A,B,C,D,E,F\}$

Order of vertex addition: $A, B, C, D, E, F$ . Edges: $AB, BC, BD, DE, DF$ . Total $= 16$ .

(Same total as Kruskal's, as expected — but the MST may use slightly different edges if there are tied weights.)

Prim's on a distance matrix.

The matrix layout makes Prim's very systematic. Edexcel convention:

Number the order in which COLUMNS are labelled (visited).
CROSS OUT the row corresponding to each visited vertex.
To find the next vertex: scan all LABELLED COLUMNS, looking for the smallest entry in an UNLABELLED (un-crossed) ROW.
The vertex corresponding to that row is the next one to visit; circle or note the edge.

Worked example. Matrix (from the topical worked example):

	A	B	C	D	E
A	—	4	9	2	7
B	4	—	5	3	8
C	9	5	—	6	1
D	2	3	6	—	5
E	7	8	1	5	—

Start at $A$ ⇒ label col $A$ (order 1), cross row $A$ . Scan col $A$ for smallest entry in rows $B, C, D, E$ : $\min(4, 9, 2, 7) = 2$ at row $D$ . Edge $AD$ . Label col $D$ (order 2), cross row $D$ .

Now scan cols $A$ AND $D$ for smallest entry in rows $B, C, E$ :

Row $B$ : cols $A=4, D=3$ . Min $= 3$ .
Row $C$ : cols $A=9, D=6$ . Min $= 6$ .
Row $E$ : cols $A=7, D=5$ . Min $= 5$ .

Overall min $= 3$ in row $B$ via column $D$ . Edge $DB$ . Label col $B$ (order 3), cross row $B$ .

Repeat: min in rows $C, E$ via cols $A, B, D$ :

Row $C$ : cols $A=9, B=5, D=6$ . Min $=5$ .
Row $E$ : cols $A=7, B=8, D=5$ . Min $=5$ .

Tie at $5$ . Standard tie-break: alphabetically first ⇒ row $C$ , via col $B$ . Edge $BC$ . Label col $C$ (order 4).

Repeat: min in row $E$ via cols $A, B, C, D$ = $\min(7, 8, 1, 5) = 1$ via col $C$ . Edge $CE$ . Label col $E$ (order 5).

Edges: $AD(2), DB(3), BC(5), CE(1)$ . Total $= 11$ .

Start anywhere; grow the tree one vertex at a time.
Shortest crossing edge each step.
Matrix form: label columns, cross rows, scan labelled cols.
Never need a cycle check.

Kruskal vs Prim: when to use which

Kruskal for edge lists; Prim for distance matrices.

Both produce a minimum spanning tree. They differ in HOW they choose edges.

Aspect	Kruskal	Prim
Edge ordering	Global (sort all edges)	Local (next vertex's edges)
Cycle check	Required at every step	Not required
Best input	List of edges	Distance matrix or drawn graph
Implementation	Edge-by-edge	Vertex-by-vertex
When ties	May produce different MST	May produce different MST

Practical exam advice.

If the question gives a LIST of edges (e.g. flight times), use KRUSKAL.
If it gives a DISTANCE MATRIX, use PRIM (matrix form).
If it gives a DRAWN graph, either works — but PRIM is faster because you can scan the diagram visually for the smallest crossing edge.

Both algorithms produce the SAME total weight (the MST weight is unique even when the tree isn't).

Edge cases.

If the graph is DISCONNECTED, no spanning tree exists. Kruskal will halt with fewer than $n - 1$ accepted edges; Prim cannot reach disconnected components.
If the graph has equal-weight edges, multiple MSTs may exist — pick one consistent tie-break rule.

Both correct; both produce same total weight.
Kruskal: list of edges.
Prim: matrix or drawn graph.
Disconnected graphs: no spanning tree.

Quick recap

Graph = vertices + edges; degree = number of incident edges.
Handshaking: $\sum \deg(v) = 2|E|$ .
Tree: connected, $n - 1$ edges, no cycles.
MST has $n - 1$ edges and minimum total weight.
Kruskal: sort edges, add if no cycle, stop at $n - 1$ .
Prim: start anywhere, add shortest edge to unvisited vertex.
Prim matrix: label columns, cross rows, scan labelled columns.
Both algorithms give the same MST weight.

Memorise this

Verbatim phrases and definitions Edexcel mark schemes credit.

Tree on $n$ vertices has exactly $n - 1$ edges.
Handshaking: $\sum \deg(v) = 2|E|$ .
Euler planar: $V - E + F = 2$ (NOT in the booklet).
Kruskal: sort edges; accept non-cycle; stop at $n-1$ .
Prim: from current tree, shortest crossing edge.
Prim matrix: label visited columns, cross visited rows, scan.

How it’s examined

Algorithms on Graphs appears as a $10$ - $13$ -mark question on every WDM01/01 paper. Standard format: (a) graph terminology — degrees, simple/connected/tree ( $2$ - $3$ marks); (b) apply Kruskal's OR Prim's to find an MST ( $6$ - $8$ marks); (c) state the total weight ( $1$ mark); (d) compare the two algorithms or explain a feature ( $2$ - $3$ marks). Marks lost: missing rejection rows in Kruskal, doing a cycle check in Prim, mis-applying the matrix labelling/crossing rule, forgetting the $n - 1$ termination. Always state the order of edge acceptance and total weight.

Sources: Pearson Edexcel International Advanced Level Mathematics specification (2018 — current for 2026 onwards); Edexcel IAL Mathematical Formulae and Statistical Tables (2018); WDM01/01 Examiner Reports — January 2023, June 2023, January 2024, June 2024. Last reviewed 2026-05-12.

Take this whole topic with you

Step-by-step worked examples — Algorithms on graphs

Step-by-step solutions to past-paper-style questions on algorithms on graphs, written exactly the way a tutor would explain them at the board.

1Identify graph features (4 marks, D1)
Core• Adapted from WDM01/01 January 2024 Q4(a)• graph terminology, degree
Question
A graph $G$ has vertices $\{A, B, C, D, E\}$ and edges $\{AB, AC, BC, BD, CE, DE\}$ . (a) State the degree of each vertex. (b) Is $G$ a simple graph? (c) Is $G$ connected? (d) Does $G$ have any cycles?
Step-by-step solution
1. Step 1
  List adjacencies. $A: B, C$ ; $B: A, C, D$ ; $C: A, B, E$ ; $D: B, E$ ; $E: C, D$ .
2. Step 2
  (a) Degrees: $\deg(A) = 2$ , $\deg(B) = 3$ , $\deg(C) = 3$ , $\deg(D) = 2$ , $\deg(E) = 2$ .
  
  Check handshaking: $\sum \deg = 2 + 3 + 3 + 2 + 2 = 12 = 2 \times 6 = 2E$ . ✓
3. Step 3
  (b) Simple? No loops (no vertex connects to itself); no multiple edges (each pair appears at most once). Yes, $G$ is simple. ✓
4. Step 4
  (c) Connected? Trace a path from any vertex to any other. $A - B - D - E - C$ visits every vertex. Yes, $G$ is connected. ✓
5. Step 5
  (d) Cycles? $A - B - C - A$ is a cycle of length $3$ . Also $B - D - E - C - B$ is a cycle of length $4$ . Yes — $G$ has cycles.
Answer
(a) $\deg(A)=2, \deg(B)=3, \deg(C)=3, \deg(D)=2, \deg(E)=2$ . (b) Yes, simple. (c) Yes, connected. (d) Yes — e.g. cycle $A$ - $B$ - $C$ - $A$ .
Examiner tip
B1 each correct degree (with handshaking check). B1 simple (justify: no loops, no multi-edges). B1 connected (give a path). B1 cycle (exhibit one). Edexcel awards justification marks — never just answer 'yes/no' without a reason.

2Minimum spanning tree by Kruskal's algorithm (6 marks, D1)

Extended• Adapted from WDM01/01 June 2024 Q4• Kruskal, MST

Question

A network has vertices $A, B, C, D, E, F$ and edges with weights: $AB = 3$ , $AC = 5$ , $AD = 6$ , $BC = 2$ , $BD = 4$ , $CD = 7$ , $CE = 8$ , $DE = 3$ , $DF = 4$ , $EF = 5$ . Use KRUSKAL'S ALGORITHM to find a minimum spanning tree. State the total weight.

Step-by-step solution

Step 1

List edges in increasing weight.

Edge	Weight	Action
$BC$	$2$	accept
$AB$	$3$	accept
$DE$	$3$	accept
$BD$	$4$	accept
$DF$	$4$	accept
$AC$	$5$	reject (would form cycle $A$ - $B$ - $C$ - $A$ )
$EF$	$5$	reject (would form cycle $D$ - $E$ - $F$ - $D$ )
$AD$	$6$	reject (cycle)
$CD$	$7$	reject
$CE$	$8$	reject

Stop when $5 = n - 1 = 6 - 1$ edges are accepted.

Step 2
Order of acceptance. $BC \to AB \to DE \to BD \to DF$ .

After $BD$ is accepted, $A, B, C, D, E$ are all connected via the tree; adding $DF$ brings in $F$ .
Step 3
Tree edges: $BC, AB, DE, BD, DF$ .

Total weight: $2 + 3 + 3 + 4 + 4 = 16$ .

Answer

MST edges $BC, AB, DE, BD, DF$ . Total weight $= 16$ .

Examiner tip

B1 list edges in non-decreasing weight order. M1 attempt Kruskal's (correct first two accepted edges). A1 correct acceptances. A1 correct rejections with cycle-justification. A1 total weight. B1 state $n - 1$ termination. Edexcel requires you to show the REJECTED edges with the reason (cycle) — not just the accepted ones.

3MST by Prim's algorithm (list form) (5 marks, D1)
Extended• Adapted from WDM01/01 January 2024 Q4(b)• Prim, MST
Question
Apply PRIM'S ALGORITHM to the same network ( $AB=3, AC=5, AD=6, BC=2, BD=4, CD=7, CE=8, DE=3, DF=4, EF=5$ ) starting from vertex $A$ . State the order in which vertices are added and the total weight.
Step-by-step solution
1. Step 1
  Start. Tree $= \{A\}$ . Edges from $A$ : $AB=3, AC=5, AD=6$ . Minimum is $AB = 3$ . Add $B$ .
2. Step 2
  Tree $= \{A, B\}$ . Crossing edges to unvisited vertices: $BC=2, AC=5, BD=4, AD=6$ . Minimum $BC = 2$ . Add $C$ .
3. Step 3
  Tree $= \{A, B, C\}$ . Crossing edges: $BD=4, AD=6, CD=7, CE=8$ . Minimum $BD = 4$ . Add $D$ .
4. Step 4
  Tree $= \{A, B, C, D\}$ . Crossing edges: $DE=3, DF=4, CE=8$ . Minimum $DE = 3$ . Add $E$ .
5. Step 5
  Tree $= \{A, B, C, D, E\}$ . Crossing edges: $DF=4, EF=5$ . Minimum $DF = 4$ . Add $F$ .
6. Step 6
  All 6 vertices added. Order: $A \to B \to C \to D \to E \to F$ . Edges chosen: $AB, BC, BD, DE, DF$ . Total $= 3 + 2 + 4 + 3 + 4 = 16$ . ✓ (Matches Kruskal's.)
Answer
Order of vertex addition: $A, B, C, D, E, F$ . Edges: $AB, BC, BD, DE, DF$ . Total weight $= 16$ .
Examiner tip
M1 attempt Prim's starting from $A$ . A1 each correct vertex addition (with weight). A1 final edge list. B1 total weight. Edexcel mark schemes expect you to STATE each crossing edge considered at each step — not just the chosen one. Awarding scheme: 1 mark per correct addition row.
4Prim's algorithm on a distance matrix (7 marks, D1)
Extended• Adapted from WDM01/01 June 2024 Q5• Prim, matrix form, MST
Question
The distance matrix below represents a weighted graph (dashes = no edge). Apply Prim's algorithm starting from $A$ .

A B C D E
A — 4 9 2 7
B 4 — 5 3 8
C 9 5 — 6 1
D 2 3 6 — 5
E 7 8 1 5 —

List the edges chosen in order, and give the total weight.
Step-by-step solution
1. Step 1
  Step 1. Label column $A$ (start). Cross out row $A$ . Scan labelled column ( $A$ ) for the smallest unlabelled-row entry.
  
  Row $A$ values in column $A$ ? — none (diagonal). Scan column $A$ : $B=4, C=9, D=2, E=7$ . Minimum $= 2$ (row $D$ ). Add edge $AD$ (weight $2$ ). Label column $D$ , cross out row $D$ .
2. Step 2
  Step 2. Labelled columns: $A, D$ . Crossed rows: $A, D$ . Unlabelled rows: $B, C, E$ .
  
  For each unlabelled row, find minimum in labelled columns:
  
  Row $B$ : col $A = 4$ , col $D = 3$ . Min $= 3$ (via $D$ ).
  
  Row $C$ : col $A = 9$ , col $D = 6$ . Min $= 6$ (via $D$ ).
  
  Row $E$ : col $A = 7$ , col $D = 5$ . Min $= 5$ (via $D$ ).
  
  Smallest overall $= 3$ , from $D$ to $B$ . Add edge $DB$ (weight $3$ ). Label column $B$ , cross out row $B$ .
3. Step 3
  Step 3. Labelled columns: $A, B, D$ . Unlabelled rows: $C, E$ .
  
  Row $C$ : $A=9, B=5, D=6$ . Min $=5$ (via $B$ ).
  
  Row $E$ : $A=7, B=8, D=5$ . Min $=5$ (via $D$ ).
  
  Tie at $5$ . Resolve by choosing the alphabetically first vertex — pick $C$ (via $BC$ ). Add edge $BC$ (weight $5$ ). Label column $C$ .
4. Step 4
  Step 4. Labelled columns: $A, B, C, D$ . Unlabelled row: $E$ .
  
  Row $E$ : $A=7, B=8, C=1, D=5$ . Min $=1$ (via $C$ ).
  
  Add edge $CE$ (weight $1$ ). Label column $E$ . All $5$ columns now labelled — stop.
5. Step 5
  Edges chosen (in order): $AD, DB, BC, CE$ . (That's $n - 1 = 4$ edges for $n = 5$ vertices.)
  
  Total weight $= 2 + 3 + 5 + 1 = 11$ .
Answer
Edges (in order): $AD(2), DB(3), BC(5), CE(1)$ . Total $= 11$ .
Examiner tip
M1 label start column and cross start row. A1 each correct edge addition ( $\times 4$ ). A1 final total. Edexcel mark schemes track every label/cross-out — present a tidy ANNOTATED matrix with numbered columns. Tie-breaking: take the alphabetically first vertex (or as stated in the question).
5Compare Kruskal's and Prim's (3 marks, D1)
Core• Adapted from WDM01/01 January 2023 Q5• comparison, MST
Question
State ONE advantage of Kruskal's algorithm over Prim's, and ONE advantage of Prim's over Kruskal's.
Step-by-step solution
1. Step 1
  Kruskal's advantage. Edges are sorted globally, so it is easy to apply when the graph is given as a LIST of edges (e.g. a railway timetable). No need to draw the network — sort the edges and check for cycles.
2. Step 2
  Prim's advantage. Works directly on a DISTANCE MATRIX and never requires a separate cycle check — by construction it only adds a vertex not already in the tree. Faster to implement on dense graphs.
3. Step 3
  Edexcel-friendly phrasing.
  
  Kruskal: 'Easy to apply when edges are listed; no graph diagram needed.'
  
  Prim: 'No cycle check required — picks the shortest edge to an unconnected vertex; works well on a matrix.'
Answer
Kruskal: easy to apply when graph is given as a list of edges (no diagram needed); just sort and check cycles. Prim: no cycle check required (vertex-based, not edge-based); works directly on a distance matrix.
Examiner tip
B1 advantage of Kruskal (sorting by weight / list form). B1 advantage of Prim (no cycle check / matrix form). B1 phrased clearly with reasoning. Standard exam-style comparison; the mark scheme accepts multiple valid answers.

Key Formulae — Algorithms on graphs

The formulae you need to memorise for algorithms on graphs on the Pearson Edexcel IAL XMA01 / YMA01 paper, with every variable defined in plain English and a note on when to use it.

Handshaking lemma
$\sum_{v \in V} \deg(v) \;=\; 2|E|$
$\deg(v)$
degree of vertex $v$
$|E|$
number of edges
When to use
Cross-check the sum of degrees equals twice the number of edges. Useful sanity check whenever you list adjacencies. NOT in the IAL formula booklet.
Example
$5$ -vertex graph with degrees $2,3,3,2,2$ : sum $= 12 = 2 \times 6 \Rightarrow 6$ edges.
Euler's formula (planar graph)
$V - E + F \;=\; 2$
$V$
vertices
$E$
edges
$F$
faces (including the outer unbounded face)
When to use
Connected PLANAR graph (one that can be drawn in the plane without crossings). NOT in the IAL formula booklet.
Example
Cube graph drawn as a planar diagram: $V = 8, E = 12$ ; so $F = 2 + E - V = 6$ .
Spanning tree edge count
$\text{Edges in any spanning tree of an } n\text{-vertex connected graph} \;=\; n - 1$
$n$
number of vertices
When to use
Termination condition for Kruskal's and Prim's: stop when $n - 1$ edges are accepted. NOT in the formula booklet.
Example
$6$ vertices ⇒ MST has $5$ edges.

Key Definitions and Keywords — Algorithms on graphs

Definitions to memorise and the exact keywords mark schemes credit for algorithms on graphs answers — sharpened from recent examiner reports for the 2026 Pearson Edexcel IAL XMA01 / YMA01 sitting.

Vertex (node)
Examiner keyword
A point in a graph. Plural: vertices. Sometimes called a 'node'. Denoted by upper-case letters or numbers.
Edge (arc)
Examiner keyword
A line joining two vertices. Sometimes called an 'arc'. May be directed (arrow) or undirected. May have a numerical weight (e.g. distance, cost).
Degree of a vertex
Examiner keyword
The number of edges incident with that vertex. Loops count twice. A vertex is EVEN/ODD according to whether its degree is even/odd.
Simple graph
A graph with no loops (no edge from a vertex to itself) and no multiple edges (at most one edge between each pair of vertices).
Connected graph
Examiner keyword
A graph where there is a path between every pair of vertices. A disconnected graph splits into two or more components.
Tree
Examiner keyword
A connected graph with no cycles. Equivalently, a connected graph with exactly $n - 1$ edges on $n$ vertices.
Spanning tree
Examiner keyword
A tree that includes every vertex of the original graph. A spanning tree of an $n$ -vertex graph has $n - 1$ edges.
Minimum spanning tree (MST)
Examiner keyword
A spanning tree with the smallest possible total edge weight. Found by Kruskal's or Prim's algorithm.
Kruskal's algorithm
Examiner keyword
Sort edges in increasing weight; consider each in turn; ACCEPT an edge if it does not form a cycle with previously accepted edges; REJECT otherwise; stop when $n - 1$ edges are accepted.
Prim's algorithm
Examiner keyword
Pick any starting vertex; at each step, add the SHORTEST EDGE connecting the current tree to a vertex not yet in the tree; stop when all vertices are included.
Distance matrix
A square matrix whose $(i, j)$ entry is the weight of the edge from vertex $i$ to vertex $j$ (with $\infty$ or '—' if no edge). Symmetric for undirected graphs.

Common Mistakes and Misconceptions — Algorithms on graphs

The traps other students keep falling into on algorithms on graphs questions — taken from recent Pearson Edexcel IAL XMA01 / YMA01 examiner reports and mark schemes — and how to avoid them.

✕Listing only the accepted edges in Kruskal's, not the rejected ones
WDM01/01 Examiner Reports — flagged every session
Why it happens
Rejected edges feel irrelevant.
How to avoid it
Edexcel mark schemes split marks between acceptance and rejection. ALWAYS write 'Accept $AB$ ', 'Accept $BC$ ', ' $AC$ rejected — cycle $A$ - $B$ - $C$ ', etc. Cycle justification is essential.
✕Doing a cycle check during Prim's algorithm
Why it happens
Confusing Prim with Kruskal.
How to avoid it
Prim NEVER needs a cycle check — by construction it adds an edge to a vertex NOT yet in the tree. The constraint is 'unvisited vertex', not 'no cycle'.
✕Crossing out COLUMNS instead of rows in Prim's matrix form
Why it happens
Mixing up Edexcel's convention.
How to avoid it
Edexcel convention: LABEL columns of visited vertices, CROSS OUT rows of visited vertices. Then scan labelled columns for the smallest entry in an unlabelled (un-crossed) row.
✕Assuming the MST is unique
Why it happens
Algorithms give an answer, so 'the' MST.
How to avoid it
If two edges tie in weight, there can be MULTIPLE MSTs (all with the same total weight). Choose either by the question's tie-breaking rule (usually alphabetical), but state if a tie occurs.
✕Counting a loop as contributing $1$ to the degree
Why it happens
Treating a loop like an ordinary edge.
How to avoid it
A loop contributes $2$ to the degree of its vertex (both ends are at the same vertex). Most D1 questions use simple graphs (no loops) — but the rule matters for handshaking checks.
✕Not verifying $\sum \deg = 2E$ as a sanity check
Why it happens
Just calculating degrees and moving on.
How to avoid it
A 30-second handshake check catches degree-counting errors. If $\sum \deg$ is odd, you have an error. Make this routine.

Algorithms on graphs — frequently asked questions

The things students keep getting wrong in this sub-topic, answered.

Algorithms on graphs

Detailed Study Notes

At a glance

What you’ll learn

Quick recap

Memorise this

How it’s examined

Take this whole topic with you

1Identify graph features (4 marks, D1)

2Minimum spanning tree by Kruskal's algorithm (6 marks, D1)

3MST by Prim's algorithm (list form) (5 marks, D1)

4Prim's algorithm on a distance matrix (7 marks, D1)

5Compare Kruskal's and Prim's (3 marks, D1)

Handshaking lemma

Euler's formula (planar graph)

Spanning tree edge count

Vertex (node)

Edge (arc)

Degree of a vertex

Simple graph

Connected graph

Tree

Spanning tree

Minimum spanning tree (MST)

Kruskal's algorithm

Prim's algorithm

Distance matrix

✕Listing only the accepted edges in Kruskal's, not the rejected ones

✕Doing a cycle check during Prim's algorithm

✕Crossing out COLUMNS instead of rows in Prim's matrix form

✕Assuming the MST is unique

✕Counting a loop as contributing 111 to the degree

✕Not verifying ∑deg⁡=2E\sum \deg = 2E∑deg=2E as a sanity check

Algorithms on graphs — frequently asked questions

✕Counting a loop as contributing $1$ to the degree

✕Not verifying $\sum \deg = 2E$ as a sanity check