Edexcel International A Level Maths · D1 · Decision Mathematics 1
Graphs, minimum spanning trees and Dijkstra
28 free, high-quality past-paper-style questions on Graphs, minimum spanning trees and Dijkstra for Edexcel IAL Maths, each with a full mark scheme. For when you have finished the past papers, or want to practise one topic at a time.IAL Maths notes and flashcards →Not sure of your level? Diagnostic test →Multiple choice or structured questions, with the mark scheme as a separate PDF.28 new this month · 247 marks · Updated 26 October 2026 · Created by Evan Kotronis with AI assistance · How questions are checked
1IALM-D1-2-B-01D1 · ASEasy6 marks
Six members of a chess club, Asha (A), Bruno (B), Chen (C), Dina (D), Emre (E) and Femi (F), play some games. Each game is between two members, and no pair plays more than once. The games played are A–B, A–C, A–D, B–C, B–E, C–D, C–E, D–F and E–F. The situation is modelled by a graph with a vertex for each member and an edge for each game.
Figure: graph of the games played (one edge per game); not to scale
(a)
Write down the degree of each vertex and verify that the sum of the degrees is twice the number of edges.
(2)
(b)
Explain why the graph is simple.
(1)
(c)
Find how many more games must be played so that every pair of members has played exactly once, and name the graph that would then model the games.
(2)
(d)
A seventh member joins and plays exactly one game. Explain why it is now impossible for all seven members to have played an odd number of games.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
A 3, B 3, C 4, D 3, E 3, F 2
B1
sum = 18 = 2 × 9 edges
B1
Part (b)
no member plays himself or herself (no loops) and no pair plays more than once (no multiple edges)
B1
Part (c)
every pair once is K6 with ½ × 6 × 5 = 15 edges
M1
15 − 9 = 6 more games; the graph is the complete graph K6
A1
Part (d)
seven odd degrees would have an odd sum, but the sum of the degrees must be even (twice the number of edges)
B1
Exam tip: “Explain why” answers about degrees should quote the handshaking result: the degrees add up to twice the number of edges, so the number of odd vertices is even.
A park has six fountains J, K, L, M, N and O joined by paths. There are paths between J and K, J and L, K and L, K and M, L and M, L and N, M and N, M and O, and N and O. No other paths exist, and no two paths join the same pair of fountains.
Figure: the fountains and paths; not to scale
(a)
Write down the adjacency matrix for the graph of fountains and paths.
(2)
(b)
Use the degrees of the vertices to explain whether the graph is Eulerian, semi-Eulerian or neither.
(2)
(c)
A gardener wants to walk along every path exactly once. State where the walk must start and finish, and give a possible order of fountains.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
6 × 6 symmetric matrix with 0s on the leading diagonal
connected with exactly two odd vertices, K and N, so semi-Eulerian
A1
Part (c)
start at K and finish at N, or the reverse
B1
e.g. K J L K M L N M O N — any valid trail using all 9 paths once
B1
Common error: Saying the graph is “not Eulerian, so the walk is impossible”. Semi-Eulerian graphs do have a trail through every edge once; it just cannot finish where it started.
A company is linking the computers in six offices, A to F, with cable. The possible cable routes and their lengths, in metres, are: AB 14, AC 9, AD 17, BC 10, BE 8, CD 12, CE 11, CF 20, DF 13, EF 15. The company wants every office connected using the least total length of cable.
Figure: possible cable routes, lengths in metres; not to scale
(a)
Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you consider them, stating any that you reject.
(4)
(b)
State the minimum total length of cable needed.
(1)
(c)
Explain why your tree has exactly five arcs.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
arcs considered in ascending order, starting BE 8, AC 9
M1
BC 10 added
A1
CE 11 rejected (it would make the cycle B–C–E)
A1
CD 12 added, DF 13 added, then stop with 5 arcs: BE, AC, BC, CD, DF
A1
Part (b)
8 + 9 + 10 + 12 + 13 = 52 m ft on their tree
B1
Part (c)
a spanning tree on 6 vertices has 6 − 1 = 5 arcs; a sixth arc would make a cycle
B1
Exam tip: Write the rejected arc in your list with the word “reject”. Leaving it out hides the step that shows you applied Kruskal's cycle check.
A cyclist wants the shortest route from the station S to the town hall T. The junctions are S, P, Q, R, U, V and T, and the cycle lanes between them, with lengths in hundreds of metres, are: SP 6, SQ 11, SR 9, PQ 4, PU 13, QR 3, QU 8, QV 12, RV 10, UV 5, UT 7, VT 9.
Figure: cycle lanes, lengths in hundreds of metres; not to scale
(a)
Use Dijkstra's algorithm to find the shortest route from S to T. Show, for each junction, the order of labelling, the final value and the working values.
(4)
(b)
State the shortest route and its length.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
a larger working value replaced by a smaller one at least once, e.g. Q 11 then 10
M1
order S, P, R, Q correct with final values 0, 6, 9, 10
A1
U: working 19, 18, final 18; V: working 19, final 19
A1
T: working 25, final 25; order of labelling U 5th, V 6th, T 7th
A1
Part (b)
trace back: T 25 − U 18 = 7 = UT, U 18 − Q 10 = 8 = QU, Q 10 − P 6 = 4 = PQ, P 6 − S 0 = 6
M1
S–P–Q–U–T, length 25 (2500 m)
A1
Common error: Writing 22 as a working value for V after labelling Q. V already has 19 (from R), and a working value is only written when it is smaller.
Figure 1 shows a graph with six vertices, P, Q, R, S, T and U.
(a)
Write down the degree of each vertex, and show that the sum of the degrees is twice the number of edges.
(2)
(b)
Give two reasons why the graph is not simple.
(1)
(c)
Write down a cycle of length 4 that passes through T, and a path from P to U that uses exactly four edges.
(2)
(d)
The loop and one of the edges joining Q and R are removed. State, with a reason, whether the graph that remains is a tree.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
P 2, Q 4, R 3, S 4, T 3, U 4 (the loop adds 2 to U)
B1
sum = 20 = 2 × 10 edges
B1
Part (b)
it has a loop (at U) and two edges joining the same pair of vertices (Q and R)
B1
Part (c)
cycle, e.g. Q–R–T–S–Q (any closed route of 4 different edges through T, no vertex repeated)
B1
path, e.g. P–Q–R–T–U or P–Q–S–T–U (no vertex repeated)
B1
Part (d)
no: it has 8 edges, but a tree on 6 vertices has exactly 5, so it contains a cycle (e.g. P–Q–S–P)
B1
Common error: Counting a loop as adding 1 to the degree. Both ends of a loop are at the same vertex, so it adds 2, and the handshaking total only works if you count it that way.
A university wants to light some of the footpaths between seven buildings, A to G, so that every building can be reached from every other along lit paths. Figure 1 shows the footpaths and their lengths in metres. The total length of lit path is to be as small as possible.
(a)
Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. List the arcs in the order in which you consider them, stating any that you reject.
(4)
(b)
Find the total length of path that is lit.
(1)
(c)
Explain why the footpath AB is not lit, even though it is shorter than EG, which is lit.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
arcs considered in ascending order of length, starting DF 22, BD 25
M1
AC 27, EF 29 added
A1
CD 30 added; AB 32 rejected (A, B, C, D are already connected: it would make the cycle A–B–D–C–A)
22 + 25 + 27 + 29 + 30 + 34 = 167 m ft on their tree
B1
Part (c)
when AB 32 is considered, A and B are already connected in the tree (A–C–D–B), so adding AB would form a cycle; when EG 34 is considered, G is not yet connected to any other building, so EG is accepted
B1
Exam tip: Kruskal stops as soon as the tree has one fewer arc than there are vertices. With 7 buildings, count to 6 accepted arcs and then stop.
Figure 1 shows the footpaths between a car park S, five viewpoints A, B, C, D and E, and a summit T. The number on each arc is the walking time in minutes. A hiker wants the quickest route from S to T.
(a)
Use Dijkstra's algorithm to find the quickest route from S to T. Show, for each vertex, the order of labelling, the final value and the working values.
(4)
(b)
State the quickest route and its time, showing how you used your working to find the route.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
a working value replaced by a smaller one at least once, e.g. C 23 then 22
M1
B 9 (order 2), A 12 (order 3)
A1
C: working 23, 22, final 22 (order 4); D: working 32, 30, final 30 (order 5)
A1
E: working 31, final 31 (order 6); T: working 39, final 39 (order 7)
Common error: Labelling A first because SA appears first. The next vertex to receive a final label is always the one with the smallest working value: here B (9), not A (12).
Figure 1 shows the trails in a nature reserve joining seven picnic sites, P to V. A ranger wants to walk along every trail exactly once.
(a)
Write down the degree of each vertex.
(1)
(b)
Explain whether the graph is Eulerian, semi-Eulerian or neither, and what this means for the ranger.
(2)
(c)
One new trail is to be built so that the ranger can walk along every trail exactly once, starting at P and finishing at S. State which two sites the new trail should join.
(1)
(d)
State the least number of new trails needed for a walk that uses every trail exactly once and returns to its starting point.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
P 3, Q 3, R 4, S 5, T 4, U 3, V 2
B1
Part (b)
four vertices, P, Q, S and U, have odd degree
M1
a connected graph needs 0 (Eulerian) or 2 (semi-Eulerian) odd vertices, so it is neither: no walk uses every trail exactly once
A1
Part (c)
the odd vertices must become just P and S, so join the other two odd vertices: Q and U
B1
Part (d)
2 (each new trail can make at most two odd vertices even, and there are four)
B1
Exam tip: Odd vertices always come in pairs. A new edge between two odd vertices makes both of them even, so plan new edges by pairing up the odd vertices.
Graph G has vertices A, B, C, D, E, F and edges AB, BC, CD, DA, AE, BE, CF, DF. Graph H has vertices 1, 2, 3, 4, 5, 6 and edges 12, 23, 31, 45, 56, 64, 14, 25. Graph K has vertices 1, 2, 3, 4, 5, 6 and edges 12, 23, 34, 45, 56, 61, 14, 25.
Figure: graphs G, H and K drawn from their edge lists; not to scale
(a)
Write down the degrees of the vertices of G, and explain why the degrees alone cannot decide whether G is isomorphic to H or to K.
(2)
(b)
Show that G and H are isomorphic.
(3)
(c)
Explain why G and K are not isomorphic.
(2)
(d)
State, with a reason, whether G is a tree.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
A 3, B 3, C 3, D 3, E 2, F 2
B1
H and K also have 8 edges and degrees 3, 3, 3, 3, 2, 2, so the degree test does not separate them
B1
Part (b)
matches E and F (degree 2) with 3 and 6, e.g. using triangles ABE ↔ 123 and CDF ↔ 546
K has no cycle of length 3 (its edges 14 and 25 join vertices three apart round the hexagon), so they cannot be isomorphic
B1
Part (d)
no: it contains a cycle (and has 8 edges, more than 6 − 1 = 5)
B1
Exam tip: To show two graphs are isomorphic, give the full matching of vertices and check every edge. To show they are not, one clear structural difference is enough.
An electricity company plans undersea cables between six islands J, K, L, M, N and O. The table gives the cost, in millions of dollars, of each cable that could be laid; a dash means that no cable can be laid between those two islands.
J
K
L
M
N
O
J
—
23
—
18
31
—
K
23
—
15
27
—
20
L
—
15
—
—
19
26
M
18
27
—
—
22
—
N
31
—
19
22
—
17
O
—
20
26
—
17
—
Figure: possible cables, costs in millions of dollars; not to scale
(a)
Use Prim's algorithm, starting at J, to find a minimum spanning tree. State the order in which the islands are added to the tree.
(4)
(b)
Find the minimum total cost.
(1)
(c)
Explain why the cable JK, cost 23, is not in your tree.
(1)
(d)
Using the table, state the number of possible cables and explain how the table shows whether the network of possible cables is simple.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
starts at J and chooses JM 18 first
M1
then MN 22
A1
then NO 17, then NL 19
A1
then LK 15; order J, M, N, O, L, K
A1
Part (b)
18 + 22 + 17 + 19 + 15 = $91 million ft on their arcs
B1
Part (c)
J and K are already joined through the tree (J–M–N–L–K), so JK would form a cycle; every tree arc on that path costs less than 23
B1
Part (d)
count the entries above the leading diagonal: 10 possible cables
B1
each entry is a single value and the diagonal is empty, so there is at most one cable per pair and no loops: simple
B1
Exam tip: On a matrix, show Prim's working: number the columns in the order the islands join and cross out each row as it joins. The final list of arcs alone does not show the method.
A national park is planning gravel paths between eight viewpoints, A to H. The paths that could be built and their lengths, in hundreds of metres, are: AB 6, AC 11, AD 9, BD 4, BE 12, CD 7, CF 10, DE 8, DF 13, EG 5, EH 14, FG 6, FH 16, GH 10. The park wants every viewpoint linked using the least total length of path.
Figure: possible paths, lengths in hundreds of metres; not to scale
(a)
Use Prim's algorithm, starting from A, to find a minimum spanning tree. List the arcs in the order in which you select them.
(4)
(b)
State the total length of the paths.
(1)
(c)
Kruskal's algorithm is applied to the same network. Write down the first six arcs that are added, and the first arc that is rejected.
(3)
(d)
State one practical difference between how the two algorithms build the tree.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
AB 6 first, then BD 4
M1
DC 7, then DE 8
A1
EG 5, then GF 6
A1
GH 10 last: AB, BD, DC, DE, EG, GF, GH
A1
Part (b)
46 hundred metres = 4.6 km ft
B1
Part (c)
BD 4, EG 5
M1
AB 6 and FG 6 (either order), CD 7, DE 8
A1
AD 9 is rejected — it makes the cycle A–B–D
A1
Part (d)
Prim's tree is connected at every stage (and needs no cycle check), whereas Kruskal's may be in separate pieces until the end
B1
Common error: Starting Prim with the shortest arc in the network (BD 4). Prim starts at the named vertex, A, and only considers arcs leaving the tree.
A delivery driver travels from the depot A to a customer at G. The roads between the places A, B, C, D, E, F and G, with journey times in minutes, are: AB 7, AC 4, AD 12, BC 2, BE 10, CD 6, CE 13, DE 5, DF 10, EF 3, EG 14, FG 8.
Figure: roads, journey times in minutes; not to scale
(a)
Use Dijkstra's algorithm to find the quickest route from A to G. Show the order of labelling, the final value and the working values at each vertex.
(6)
(b)
State the quickest route and its time, and explain how you used your working to find the route.
(2)
(c)
The road DE is closed. Find the quickest route from A to G now, and its time.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
a larger working value replaced by a smaller one at least once
M1
C 4 (1st after A) and B 6 with working values 7, 6
A1
D: working 12, 10; final 10
A1
E: working 17, 16, 15; final 15
A1
F: working 20, 18; final 18
A1
G: working 29, 26; final 26; order A, C, B, D, E, F, G
A1
Part (b)
trace back from G: 26 − 18 = 8 = FG, 18 − 15 = 3 = EF, 15 − 10 = 5 = DE, 10 − 4 = 6 = CD, 4 − 0 = 4 = AC
M1
A–C–D–E–F–G, 26 minutes
A1
Part (c)
E can now only be reached from B, C or F: A–C–B–E = 16 is best, then F = 19 (D–F gives 20)
M1
A–C–B–E–F–G, 27 minutes
A1
Exam tip: E receives three working values here (17, 16, 15). List every improving value in the order you found it: the box is the evidence that the algorithm was followed.
Six farms P, Q, R, S, T and U are to be connected by water pipes. The pipes that could be laid, with costs in thousands of dollars, are: PQ 8, PR 5, PS 11, QR 7, QT 6, RS 7, RT 9, RU 12, ST 10, SU 6, TU 8.
Figure: possible pipes, costs in thousands of dollars; not to scale
(a)
Use Kruskal's algorithm to find a minimum spanning tree, showing the order in which arcs are added. State its total cost.
(4)
(b)
Explain why the minimum spanning tree is unique even though some arcs have equal weights.
(1)
(c)
An old pipe already runs along RU and must be included in the network (its cost of 12 is still counted). Find a minimum-cost spanning tree that contains RU, and the extra cost compared with your answer to part (a).
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
PR 5 first, then QT 6 and SU 6 (either order)
M1
QR 7 and RS 7 both added (either order)
A1
stop at 5 arcs: PR, QT, SU, QR, RS
A1
total $31 000
A1
Part (b)
the tied arcs (QT, SU at 6 and QR, RS at 7) are all accepted whichever order is used, so no choice is ever made between them
B1
Part (c)
start with RU, then apply Kruskal to the remaining arcs: PR 5, QT 6, SU 6
M1
QR 7 added; RS 7 is now rejected if considered, since R–U–S are already connected
A1
RU, PR, QT, SU, QR: total $36 000, which is $5000 more
A1
Exam tip: When an arc must be included, put it in the tree first and then continue with Kruskal's algorithm as normal; other arcs that would now close a cycle with it must be rejected.
Figure 1 shows three graphs, G, H and J, each with six vertices.
(a)
Show that H and J are isomorphic.
(3)
(b)
J is drawn with edges crossing. State, with a reason, whether J is planar.
(1)
(c)
In G, every edge joins an odd-numbered vertex to an even-numbered vertex. Write down a cycle in G that passes through all six vertices and uses all three long diagonals, and explain why every cycle in G has an even number of edges.
(2)
(d)
Every vertex in all three graphs has degree 3. Explain why this does not settle whether G is isomorphic to H, and use your answer to part (c) to show that it is not.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
uses a structural feature to match vertices, e.g. the triangles P–Q–R and S–T–U in J matched to A–B–C and D–E–F in H
M1
P→A, Q→B, R→C, S→F, T→E, U→D (or another correct matching)
A1
checks all nine edges: PQ→AB, QR→BC, RS→CF, ST→FE, TU→ED, UP→DA, PR→AC, SU→FD, QT→BE
A1
Part (b)
yes: J is isomorphic to H, and H is drawn with no edges crossing
B1
Part (c)
e.g. 1–4–3–6–5–2–1 or 1–4–5–2–3–6–1 (any closed route through all six vertices using 1–4, 2–5 and 3–6)
B1
round any cycle the vertices alternate odd, even, odd, …, and the cycle must end at the vertex it started from, so it has an even number of edges
B1
Part (d)
G and H both have 6 vertices, 9 edges and every degree 3, so counting edges and degrees cannot tell them apart
B1
H contains the triangle A–B–C, a cycle with an odd number (3) of edges, but every cycle in G is even, so G is not isomorphic to H
B1
Exam tip: To prove two graphs are isomorphic, write the full vertex matching and then check every edge. To prove they are not, one structural difference (such as a triangle) is enough.
A ski resort is linking eight lift stations, A to H, with a communications cable. Figure 1 shows the links that could be laid and the cost of each, in thousands of dollars. The resort wants every station linked at the least total cost.
(a)
Use Prim's algorithm, starting at E, to find a minimum spanning tree. List the arcs in the order in which you select them, and the order in which the stations join the tree.
(4)
(b)
State the minimum total cost.
(1)
(c)
Give one reason why Prim's algorithm does not need a check for cycles.
(1)
(d)
The cost of the link FG can be renegotiated. Find the greatest whole-number cost, in thousands of dollars, for which FG would definitely be in the minimum spanning tree.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
starts at E and selects EG 8
M1
GH 7, then ED 10
A1
DB 11, then DC 13
A1
CA 9, then CF 12; stations in the order E, G, H, D, B, C, A, F
A1
Part (b)
8 + 7 + 10 + 11 + 13 + 9 + 12 = $70 000 ft
B1
Part (c)
each arc chosen joins a vertex already in the tree to one not yet in it, so it can never close a cycle
B1
Part (d)
the tree path from F to G is F–C–D–E–G
M1
its most expensive arc is DC 13, so FG enters the tree if its cost is less than 13
M1
greatest whole-number cost 12 ($12 000)
A1
Common error: Starting Prim with the cheapest arc in the whole network (GH 7). Prim begins at the named vertex, E, and only looks at arcs leaving the tree built so far.
Figure 1 shows the roads between six warehouses, P to U, with the driving time along each road in minutes. A company wants to choose roads of least total time so that every warehouse is connected to every other.
(a)
Write down the distance matrix for the network in Figure 1, using a dash where there is no direct road.
(2)
(b)
Use Prim's algorithm on your matrix, starting with row P, to find a minimum spanning tree. State the arcs in the order in which you select them and the order in which the warehouses join.
(4)
(c)
State the total time of the roads chosen.
(1)
(d)
Explain how the distance matrix shows the degree of T, and state its value.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
6 × 6 symmetric table with dashes on the leading diagonal and where there is no road
starts at P and selects PR 4 (smallest entry in row P)
M1
RQ 5, then RS 6
A1
SU 3
A1
QT 8; order P, R, Q, S, U, T
A1
Part (c)
4 + 5 + 6 + 3 + 8 = 26 minutes ft
B1
Part (d)
count the entries (not dashes) in row T: Q, R, S, U, so degree 4
B1
Exam tip: When you run Prim on a matrix, label the columns in the order the vertices join and delete each new vertex's row. Writing only the final tree does not show the method.
Figure 1 shows the roads between a railway station S, seven junctions A, B, C, D, E, F and K, and a hotel T. The number on each arc is the driving time in minutes. A taxi driver wants the quickest route from S to T.
(a)
Use Dijkstra's algorithm to find the quickest route from S to T. Show the order of labelling, the final value and the working values at each vertex.
(6)
(b)
State the quickest route from S to T and its time.
(2)
(c)
On one trip the taxi must first pick up a passenger at E. Find the quickest route from S to T that passes through E, and its time.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
a working value replaced by a smaller one at least once
M1
C 4 (order 2), A 6 (order 3), B: working 10, 9, final 9 (order 4)
A1
D: working 15, 14, final 14 (order 5)
A1
E: working 16, final 16 (order 6); K: working 18, final 18 (order 7)
S to E: 16 from the working, route S–C–E; E to T: E–K–F–T = 3 + 2 + 5 = 10 (quicker than E–F–T = 11)
M1
S–C–E–K–F–T, 26 minutes
A1
Exam tip: For a route that must visit a given vertex, split it into two shortest routes: start to that vertex (read from your Dijkstra boxes) and that vertex to the end.
Figure 1 shows the corridors in a hospital between the entrance S, five wards A, B, C, D and E, and the theatre T. To control the flow of people, some corridors are one-way, in the direction of the arrow; the others are two-way. The number on each arc is the walking time in seconds.
(a)
Use Dijkstra's algorithm to find the quickest route from S to T. Show the order of labelling, the final value and the working values at each vertex.
(5)
(b)
State the quickest route from S to T and its time.
(2)
(c)
Explain why the quickest route from S to E is not S → A → C → E, even though it would take only 11 seconds.
(1)
(d)
The direction of the one-way corridor between C and E is reversed, so that it now runs from C to E. Find the quickest route from S to T now, and its time.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
uses each one-way corridor only in the direction of its arrow
M1
A 5 (order 2), C 9 (order 3)
A1
B: working 10, final 10 (order 4); D: working 16, 15, final 15 (order 5)
A1
E: working 17, final 17 (order 6); D → E gives 24, not written
A1
T: working 23, final 23 (order 7); E → T gives 17 + 8 = 25, not written
the corridor between C and E is one-way from E to C, so it cannot be used from C to E
B1
Part (d)
E can now be reached as S → A → C → E = 5 + 4 + 2 = 11, then E → T gives 19
M1
S → A → C → E → T, 19 seconds
A1
Common error: Using a one-way arc against its arrow when updating working values. From a newly labelled vertex, only update vertices you can travel to along an arc.
Figure 1 shows a graph G with vertices A, B, C, D and E, and four graphs T1, T2, T3 and T4 drawn on the same five vertices.
(a)
For each of T1, T2, T3 and T4, state whether it is a spanning tree of G, giving a reason in each case.
(4)
(b)
Find the degree of each vertex of G, and hence state whether G is Eulerian, semi-Eulerian or neither.
(2)
(c)
Write down the edges that must be added to G to make the complete graph K5, and explain why K5 is Eulerian.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
T1: yes: it uses only edges of G, includes all five vertices, is connected and has no cycle (4 edges)
B1
T2: no: it contains the cycle A–C–D–A (and is not connected)
B1
T3: no: it does not include vertex D, so it does not span G
B1
T4: no: AE is not an edge of G, so T4 is not a subgraph of G
B1
Part (b)
A 3, B 3, C 4, D 3, E 3
B1
four odd vertices (A, B, D, E), so neither
B1
Part (c)
AE and BD (K5 has ½ × 5 × 4 = 10 edges; G has 8)
B1
every vertex of K5 has degree 4, which is even, and K5 is connected
B1
Exam tip: A spanning tree must pass four tests: only edges of the original graph, every vertex included, connected, and no cycles. Name the test that fails.
The table shows the lengths, in km, of the roads that directly join seven villages A to G. A dash means there is no direct road. The council wants to resurface a set of roads, of least total length, so that every village can be reached from every other on resurfaced roads.
A
B
C
D
E
F
G
A
—
12
—
9
—
—
15
B
12
—
8
—
14
—
—
C
—
8
—
11
—
7
—
D
9
—
11
—
10
—
13
E
—
14
—
10
—
6
—
F
—
—
7
—
6
—
16
G
15
—
—
13
—
16
—
Figure: roads joining the seven villages, lengths in km; not to scale
(a)
Use Prim's algorithm, starting at A, to find which roads should be resurfaced. List the arcs in the order in which you select them and state the total length.
(5)
(b)
Find the number of roads shown in the table and the degree of each village in the road network.
(2)
(c)
A walker wants to use every road exactly once. Explain why this is impossible.
(2)
(d)
A new village H is built, with roads AH 10, DH 5 and GH 8. Find the least total length of resurfaced road now needed to connect all eight villages, and show that it is no greater than before.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
AD 9 first
M1
DE 10, then EF 6
A1
FC 7, then CB 8
A1
DG 13 last
A1
total 53 km
A1
Part (b)
count the entries in each row: A 3, B 3, C 3, D 4, E 3, F 3, G 3
M1
sum 22, so 11 roads
A1
Part (c)
a trail using every edge once needs 0 or 2 odd vertices
M1
here six villages (A, B, C, E, F, G) have odd degree, so it is impossible
A1
Part (d)
Kruskal (or Prim) on the enlarged network: DH 5, EF 6, CF 7, BC 8 and GH 8 (either order)
M1
AD 9, DE 10; DG 13 is no longer needed (G joins through H)
A1
total 5 + 6 + 7 + 8 + 8 + 9 + 10 = 53 km, the same as before even with an extra village
A1
Exam tip: In a distance matrix, the number of entries in a row (not counting dashes) is the degree of that vertex, and half the total number of entries is the number of arcs.
A town centre has one-way streets, modelled by a directed network. The junctions are S, A, B, C, D, E and T, and each arc below can only be travelled in the direction given (from the first letter to the second). Times are in minutes: S→A 4, S→B 7, A→B 2, A→C 9, B→C 5, B→D 11, C→D 3, C→E 8, D→T 6, E→T 3, D→E 4, T→A 10, E→B 3.
Figure: one-way streets, times in minutes (arrows show the direction of travel); not to scale
(a)
Explain why the adjacency matrix of this directed network is not symmetric.
(1)
(b)
Use Dijkstra's algorithm to find the quickest route from S to T, showing the order of labelling, final values and working values.
(6)
(c)
State the quickest route from S to T and its time.
(2)
(d)
Explain why there is no route from T back to S, and find the quickest time from T to C.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
the entry in row X, column Y counts arcs from X to Y; e.g. S→A exists but A→S does not, so the matrix is not symmetric
B1
Part (b)
uses arcs only in their given directions
M1
A 4 (order 2); B working 7, 6, final 6 (order 3)
A1
C working 13, 11, final 11 (order 4)
A1
D working 17, 14, final 14 (order 5)
A1
E working 19, 18, final 18 (order 6)
A1
T working 20, final 20 (order 7); E→T gives 21, not written
no arc ends at S (every arc at S points away from it), so S cannot be reached
B1
from T the only arc is T→A 10; then A→B→C = 2 + 5 (A→C direct is 9)
M1
T → A → B → C, 17 minutes
A1
Common error: Using a one-way street in the wrong direction. In a digraph, only update a working value at Y if there is an arc from the newly labelled vertex to Y.
A broadband provider can lay fibre-optic cable between eight exchanges, A to H. The possible links and their lengths, in km, are: AB 9, AC 14, AD 7, BC 4, BE 11, CD 12, CF 6, DG 10, EF 5, EH 13, FG 8, FH 9, GH 15. Exchange A is the main hub.
Figure: possible links, lengths in km; not to scale
(a)
Use Dijkstra's algorithm to find the shortest distance from A to every other exchange. Show the order of labelling, final values and working values.
(6)
(b)
State the shortest route from A to H.
(1)
(c)
Use Kruskal's algorithm to find a minimum spanning tree, listing arcs in the order in which they are added, and state its total length.
(3)
(d)
A direct link AH of length x km is proposed. Find the range of values of x for which (i) AH would shorten the shortest route from A to H, (ii) AH would definitely be in the minimum spanning tree.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
a larger working value replaced by a smaller one at least once
M1
D 7 (order 2), B 9 (order 3)
A1
C: working 14, 13, final 13 (order 4)
A1
G 17 (order 5), F 19 (order 6)
A1
E 20 (order 7)
A1
H: working 32, 28, final 28 (order 8)
A1
Part (b)
A–B–C–F–H (28 km) ft
B1
Part (c)
BC 4, EF 5, CF 6, AD 7
M1
FG 8, then AB 9 and FH 9 (either order); stop at 7 arcs
A1
total 48 km
A1
Part (d)
(i) x < 28, the current shortest distance
B1
(ii) the tree path from A to H is A–B–C–F–H, whose longest arc is 9 (AB or FH)
M1
AH replaces one of them only if x < 9
A1
Exam tip: A new arc enters a minimum spanning tree only if it is lighter than the heaviest arc on the tree path between its ends: that arc is the one it replaces.
The table gives the times, in minutes, for a maintenance vehicle to drive along the roads that directly connect seven depots P to V. A dash means there is no direct road.
P
Q
R
S
T
U
V
P
—
8
5
—
—
—
—
Q
8
—
2
7
—
—
—
R
5
2
—
—
10
—
—
S
—
7
—
—
3
6
—
T
—
—
10
3
—
—
12
U
—
—
—
6
—
—
4
V
—
—
—
—
12
4
—
Figure: roads between the depots, times in minutes; not to scale
(a)
Explain how the table shows that there are exactly 9 roads, and find which depots have odd degree.
(2)
(b)
Use Dijkstra's algorithm to find the quickest route from P to V, showing the order of labelling, final values and working values.
(5)
(c)
State the quickest route from P to V and its time.
(2)
(d)
Find the minimum total time of roads that would connect all seven depots, and state whether your route from part (c) uses only roads in this minimum spanning tree.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
18 non-dash entries, each road appearing twice (symmetric), so 18 ÷ 2 = 9 roads
B1
row counts P 2, Q 3, R 3, S 3, T 3, U 2, V 2: odd vertices Q, R, S, T
B1
Part (b)
a larger working value replaced by a smaller one at least once (Q: 8 then 7)
M1
R 5 (order 2), Q 7 (order 3)
A1
S 14 (order 4), T 15 (order 5); T keeps 15 because 14 + 3 = 17 is larger
Kruskal: QR 2, ST 3, UV 4, PR 5, SU 6, QS 7: total 27 minutes
B1
yes: PR, RQ, QS, SU and UV are all tree arcs (here the tree path is the shortest route, which is not true in general)
B1
Exam tip: With a table instead of a diagram, sketch the network quickly before starting Dijkstra. It is much easier to fill boxes and trace back on a drawing.
Figure 1 shows the roads between ten villages, A to J, with their lengths in km. In winter the council grits a set of roads of least total length so that every village can be reached from every other on gritted roads.
(a)
Use Kruskal's algorithm to find which roads should be gritted. List the arcs in the order in which you consider them, stating any that you reject.
(4)
(b)
Find the total length of road that is gritted.
(1)
(c)
A gritting lorry is based at A. Use Dijkstra's algorithm to find the shortest distance from A to J, showing the order of labelling, the final values and the working values.
(5)
(d)
State the shortest route from A to J.
(1)
(e)
Find the length of the route from A to J that uses only gritted roads, and explain why it is longer than your answer to part (c).
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
FG 3, EF 4 first
M1
BD 5 and HI 5 (either order), CD 6 and GH 6 (either order)
A1
BC 7 rejected (cycle B–C–D–B)
A1
AB 8 and IJ 8 (either order), DE 9 (if GI 9 is considered before DE, it is rejected: cycle G–H–I–G); stop with 9 arcs
A1
Part (b)
3 + 4 + 5 + 5 + 6 + 6 + 8 + 8 + 9 = 54 km ft
B1
Part (c)
a working value replaced by a smaller one at least once
M1
B 8, C 11, D 13 (orders 2, 3, 4)
A1
E: working 24, 22, final 22; F: working 24, 23, final 23 (orders 5, 6)
A1
G: working 34, 26, final 26; H: working 39, 32, final 32; I: working 41, 35, final 35 (orders 7, 8, 9)
A1
J: working 44, 43, final 43 (order 10)
A1
Part (d)
A–B–D–F–G–I–J (43 km) ft
B1
Part (e)
the tree path is A–B–D–E–F–G–H–I–J = 8 + 5 + 9 + 4 + 3 + 6 + 5 + 8 = 48 km
B1
a minimum spanning tree minimises the total length of the whole network, not the distance between a particular pair of vertices; the shortest route uses DF and GI, which are not in the tree
B1
Exam tip: Minimum spanning trees and shortest routes answer different questions. Do not read a shortest route off a minimum spanning tree; run Dijkstra on the full network.
Figure 1 shows a network with vertices S, A, B, C, D, E and T. The lengths of the arcs AC, ET and DE are unknown and are marked x, y and z; x, y and z are positive integers. Dijkstra's algorithm has been applied correctly from S, and Figure 1 shows the completed box at each vertex: the order of labelling, the final value and the working values. A working value is written only when it is smaller than the value already there.
(a)
Use the boxes to find a shortest route from S to T, and its length.
(2)
(b)
Find the value of x, explaining your reasoning.
(2)
(c)
Find the set of possible values of y, explaining your reasoning.
(2)
(d)
Find the least possible value of z, explaining your reasoning.
(2)
(e)
Given that y = 8 and z = 7, use Prim's algorithm starting at S to find a minimum spanning tree, and state its total length.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
trace back: T 21 − D 12 = 9 = DT, D 12 − B 3 = 9 = BD, B 3 − 0 = 3 = SB
M1
S–B–D–T, length 21
A1
Part (b)
C's first working value 12 = 3 + 9 came from B; the smaller value 11 was written when A (final 5) was labelled, via AC
M1
5 + x = 11, so x = 6
A1
Part (c)
when E was labelled (16), T already had 21, and no new working value was written at T
M1
so 16 + y ≥ 21 (equality allowed, as an equal value is not written), giving y ≥ 5, y an integer (accept y ∈ {5, 6, 7, …})
A1
Part (d)
D was labelled (12) before E, and E's only working value is 16 (from C), so no smaller value came from D
M1
12 + z ≥ 16, so z ≥ 4; least value 4
A1
Part (e)
SB 3, BA 2
M1
AC 6, CD 4, CE 5
A1
ET 8; total 28 ft on their x
A1
Exam tip: Every working value in a Dijkstra box is (final value of the vertex just labelled) + (arc length). Reading a box backwards like this lets you recover unknown arcs, or show that an arc was too long to improve a value.
A water company has a reservoir H and seven towns A to G. Figure 1 shows the pipelines that could be built and the cost of each, in thousands of dollars. The company wants every town connected to the reservoir, directly or through other towns, at the least total cost.
(a)
Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you consider them, stating any that you reject.
(5)
(b)
State the total cost of this tree.
(1)
(c)
For safety reasons, exactly one pipeline may leave the reservoir H. Find the minimum cost of a network that meets this condition, and the extra cost compared with part (b).
(3)
(d)
Use the degrees of the vertices to explain why an inspector cannot travel along every possible pipeline route exactly once.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
EF 5, AH 6, BH 7 first
M1
DE 8, CH 9 added
A1
BC 10 rejected; DH 11 added
A1
AB 12, EH 13, CD 14 all rejected (each makes a cycle)
A1
FG 15 added; stop with 7 arcs: EF, AH, BH, DE, CH, DH, FG
A1
Part (b)
5 + 6 + 7 + 8 + 9 + 11 + 15 = $61 000 ft
B1
Part (c)
H must be a vertex of degree 1: find a minimum spanning tree of the towns A to G alone, then join H by its cheapest arc
M1
the towns form the ring A–B–C–D–E–F–G–A; drop its most expensive arc, GA 18: 12 + 10 + 14 + 8 + 5 + 15 = 64
M1
add AH 6: $70 000, which is $9000 more
A1
Part (d)
each town has degree 3 and H has degree 7, so all eight vertices are odd
M1
a route using every arc once needs 0 or 2 odd vertices, so it is impossible
A1
Exam tip: When a vertex must have degree 1 in the tree, remove it, find the minimum spanning tree of what is left, then attach the vertex by its cheapest arc.
Figure 1 shows a grid of streets in a city centre. A bus travels from junction A to junction T. The number on each street is the driving time in minutes.
(a)
Use Dijkstra's algorithm to find the quickest route from A to T. Show the order of labelling, the final value and the working values at each junction.
(6)
(b)
State the quickest route and its time.
(2)
(c)
A new street is proposed from E directly to T, taking t minutes. Find the range of values of t for which the new street would give a quicker journey from A to T.
(2)
(d)
Without the new street, traffic lights cause a delay of 2 minutes at every junction the bus passes through (not A or T). Find the quickest route from A to T now, and its time.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
a working value replaced by a smaller one at least once
the quickest time from A to E is 7, so the new route takes 7 + t
M1
7 + t < 21, so t < 14
A1
Part (d)
a route with k streets passes through k − 1 junctions, adding 2(k − 1) minutes; the route in (b) has 6 streets: 21 + 10 = 31
M1
every route from A to T has an even number of streets, at least 4; any route of 6 or more streets takes at least 21 + 10 = 31, so compare the six 4-street routes: ADEHT 23, ABCFT 24, ADEFT 24, ABEHT 30, ADGHT 32, ABEFT 31
M1
A–D–E–H–T, 23 + 6 = 29 minutes
A1
Exam tip: A fixed delay at each junction is equivalent to adding the delay to every street (and taking it off once at the end). It favours routes with fewer streets, so the quickest route can change.
We use essential cookies to make this site work. With your permission we'd also use analytics and advertising cookies to understand which resources help students most and how families find us. Nothing optional is set unless you accept. Privacy policy
EssentialNeeded for the site and your cookie choice to work.
Always on
AnalyticsAnonymous visit statistics that help improve the free resources.
MarketingMeasures whether ads reach the right families. Off unless you turn it on.