D1-3 Algorithms on graphs II — revision question pack

2 specification points · notes, questions, answers and worked methods

Checked against Edexcel 9FM0 section D1-3. Review basis: the qualification registry sourced from the Pearson Edexcel Level 3 Advanced GCE in Further Mathematics (9FM0) specification; registry verification recorded 17 July 2026.

How this checking works

D1-3.1 · Algorithm for finding the shortest route around a network, travelling along every edge at least once and ending at the start vertex (the Route Inspection Algorithm).

Explanation

The route inspection, or Chinese postman, problem asks for the shortest closed route that uses every arc of a network at least once. If every vertex has even order the network is Eulerian and the answer is simply the total weight of the network.
Otherwise the odd vertices must be paired up and the shortest path between each pair repeated, because repeating a path raises the order of its two endpoints by one and leaves every internal vertex even.
With four odd vertices there are exactly three pairings to test; with six there are fifteen, which is why the specification limits questions to at most four odd vertices unless extra information restricts the pairings.
Work out the shortest path for each pair, total each pairing, choose the smallest total, and add it to the weight of the network.
If the route may start and finish at different vertices, leave the two odd vertices with the largest shortest path between them unpaired and repeat the best pairing of the remaining two.

Worked example

A network of total weight $60$ has odd vertices $P$ , $Q$ , $R$ , $S$ with shortest paths $PQ=8$ , $PR=13$ , $PS=10$ , $QR=9$ , $QS=15$ , $RS=6$ . Find the length of the shortest closed route covering every arc.

1.The three pairings are $PQ+RS$ , $PR+QS$ and $PS+QR$ .
2. $PQ+RS=8+6=14$ .
3. $PR+QS=13+15=28$ .
4. $PS+QR=10+9=19$ .
5.The smallest repeat is $14$ , so the route length is $60+14=74$ .

Answer: The shortest closed route has length $74$ , repeating the shortest paths $PQ$ and $RS$ .

Common mistakes

Don't fall into the trap of pairing the odd vertices using a single direct arc when a shorter indirect path exists.
Don't fall into the trap of adding the repeats to the number of arcs rather than to the total weight of the network.
Don't fall into the trap of testing only some of the three pairings and assuming the first small total is best.

Exam tip

List all three pairings in full even when one looks obviously best; the marks are for the complete comparison, not just for the final total.

Tier 1 · Easy

1.
A connected network has total weight $84$ and every vertex has even order. State the length of the shortest closed route that travels along every arc at least once, and justify your answer.
(3)
(Total for Question 1 is 3 marks)
2.
A network has vertices $A$ to $F$ and arcs $AB=8$ , $AC=5$ , $AD=9$ , $BC=6$ , $BE=7$ , $CD=4$ , $CE=11$ , $DE=12$ , $DF=10$ , $EF=3$ . Identify the odd vertices and find the length of the shortest closed route that uses every arc at least once, starting and finishing at $A$ .
(5)
(Total for Question 2 is 5 marks)

Tier 2 · Standard

1.
A network has vertices $A$ to $F$ and arcs $AB=7$ , $AC=9$ , $AF=12$ , $BC=5$ , $BD=8$ , $CD=6$ , $CE=10$ , $DE=4$ , $DF=14$ , $EF=11$ . Find the odd vertices, the total weight, and the length of the shortest closed route covering every arc.
(7)
(Total for Question 1 is 7 marks)
2.
Explain why the arcs repeated in a route inspection problem must form paths joining odd vertices in pairs, and state how many pairings must be tested when a network has $4$ odd vertices and when it has $6$ .
(5)
(Total for Question 2 is 5 marks)
3.
A network has vertices $A$ to $G$ and arcs $AB=6$ , $AC=11$ , $AG=9$ , $BC=4$ , $BD=13$ , $CD=7$ , $CE=8$ , $DE=5$ , $DF=10$ , $EF=3$ , $EG=15$ , $FG=12$ . Identify the odd vertices and find the length of the shortest closed route covering every arc.
(7)
(Total for Question 3 is 7 marks)

Tier 3 · Hard

1.
For the network with vertices $A$ to $F$ and arcs $AB=7$ , $AC=9$ , $AF=12$ , $BC=5$ , $BD=8$ , $CD=6$ , $CE=10$ , $DE=4$ , $DF=14$ , $EF=11$ , a route must travel along every arc at least once but may start and finish at different vertices. Determine the shortest possible length and the start and finish vertices.
(8)
(Total for Question 1 is 8 marks)
2.
A network of total weight $148$ has exactly four odd vertices $P$ , $Q$ , $R$ , $S$ . The shortest paths between them are $PQ=17$ , $PR=x$ , $PS=21$ , $QR=19$ , $QS=26$ and $RS=14$ , where $x>0$ . A student claims that the shortest closed route covering every arc has length $184$ . Determine whether any value of $x$ makes the claim true, and find the shortest closed route length in terms of $x$ .
(7)
(Total for Question 2 is 7 marks)
3.
A gritting lorry must drive along every road of a network of total length $103$ kilometres and return to its depot. The network has vertices $A$ to $G$ , the odd vertices are $A$ , $B$ , $F$ and $G$ , and the shortest paths between them are $AB=6$ , $AF=21$ , $AG=9$ , $BF=15$ , $BG=15$ and $FG=12$ . The council will pay to build one new road, of length $4$ kilometres, joining $A$ directly to $F$ . Determine whether the new road shortens the gritting route.
(8)
(Total for Question 3 is 8 marks)
4.
A network has six odd vertices. Explain why $15$ pairings would normally have to be tested, and describe precisely what extra information an examiner must supply so that the problem can be set at this level.
(6)
(Total for Question 4 is 6 marks)
5.
In the network with vertices $A$ to $F$ and arcs $AB=8$ , $AC=5$ , $AD=9$ , $BC=6$ , $BE=7$ , $CD=4$ , $CE=11$ , $DE=12$ , $DF=10$ , $EF=3$ , the weight of arc $AB$ is changed to $k$ , where $k>0$ . The odd vertices remain $A$ and $B$ . Find, in terms of $k$ , the length of the shortest closed route covering every arc, distinguishing the cases that arise.
(8)
(Total for Question 5 is 8 marks)

D1-3.2 · The practical and classical Travelling Salesman problems. Determination of upper and lower bounds using minimum spanning tree methods. The nearest neighbour algorithm.

Explanation

The travelling salesman problem asks for a tour of minimum length that visits every vertex and returns to the start. In the classical problem each vertex is visited exactly once; in the practical problem a vertex may be revisited.
The classical problem is set on a complete network satisfying the triangle inequality, that is, the length of any arc is at most the sum of the lengths of the other two in its triangle. Converting the network into a complete network of shortest distances turns the practical problem into a classical one.
Since the problem cannot be solved exactly at this level, the answer is trapped between bounds. The nearest neighbour algorithm gives an upper bound: from the start vertex repeatedly go to the nearest unvisited vertex, then return to the start.
Doubling the weight of the minimum spanning tree also gives an upper bound, which short cuts can improve. A lower bound comes from deleting one vertex, finding the residual minimum spanning tree on the remaining vertices, and adding the two shortest arcs at the deleted vertex;
repeating this for every vertex and taking the largest result gives the best lower bound. When an upper bound equals a lower bound, that common value is the length of the optimal tour.

Worked example

A complete network on $A$ , $B$ , $C$ , $D$ has $AB=6$ , $AC=10$ , $AD=9$ , $BC=7$ , $BD=12$ , $CD=5$ . Find the nearest neighbour tour from $A$ and the lower bound obtained by deleting $A$ .

1.From $A$ the nearest vertex is $B$ at $6$ ; from $B$ the nearest unvisited is $C$ at $7$ ; from $C$ the only one left is $D$ at $5$ ; then $D$ back to $A$ at $9$ .
2.The tour is $ABCDA$ of length $6+7+5+9=27$ .
3.Deleting $A$ leaves $B$ , $C$ , $D$ with arcs $BC=7$ , $BD=12$ , $CD=5$ ; the residual minimum spanning tree is $CD=5$ and $BC=7$ , of weight $12$ .
4.The two shortest arcs at $A$ are $AB=6$ and $AD=9$ .
5.The lower bound is $12+6+9=27$ .

Answer: The upper bound and the lower bound are both $27$ , so the optimal tour has length exactly $27$ .

Common mistakes

Don't fall into the trap of adding the two shortest arcs of the whole network instead of the two shortest at the deleted vertex.
Don't fall into the trap of including the deleted vertex when building the residual minimum spanning tree.
Don't fall into the trap of quoting the smallest lower bound rather than the largest as the best one.

Exam tip

Always state which vertex you deleted; a lower bound is only worth marks when the examiner can see the residual tree it came from.

Tier 1 · Easy

1.
Explain the difference between the classical and the practical travelling salesman problems, and state how the practical problem is converted into a classical one.
(3)
(Total for Question 1 is 3 marks)
2.
A complete network on $A$ , $B$ , $C$ , $D$ , $E$ has $AB=14$ , $AC=20$ , $AD=23$ , $AE=12$ , $BC=9$ , $BD=18$ , $BE=25$ , $CD=11$ , $CE=17$ , $DE=21$ . Apply the nearest neighbour algorithm starting at $B$ and state the upper bound it gives.
(4)
(Total for Question 2 is 4 marks)

Tier 2 · Standard

1.
For the complete network on $A$ to $E$ with $AB=14$ , $AC=20$ , $AD=23$ , $AE=12$ , $BC=9$ , $BD=18$ , $BE=25$ , $CD=11$ , $CE=17$ , $DE=21$ , apply the nearest neighbour algorithm starting at $A$ and comment on the quality of the upper bound it produces.
(5)
(Total for Question 1 is 5 marks)
2.
For the complete network on $A$ to $E$ with $AB=14$ , $AC=20$ , $AD=23$ , $AE=12$ , $BC=9$ , $BD=18$ , $BE=25$ , $CD=11$ , $CE=17$ , $DE=21$ , find the lower bound obtained by deleting vertex $C$ .
(5)
(Total for Question 2 is 5 marks)
3.
A network has vertices $A$ to $E$ and arcs $AB=9$ , $AC=15$ , $BC=7$ , $BD=12$ , $CD=6$ , $CE=14$ , $DE=8$ , with no other direct connections. Construct the complete network of shortest distances between the five vertices.
(6)
(Total for Question 3 is 6 marks)

Tier 3 · Hard

1.
For the complete network on $A$ to $E$ with $AB=14$ , $AC=20$ , $AD=23$ , $AE=12$ , $BC=9$ , $BD=18$ , $BE=25$ , $CD=11$ , $CE=17$ , $DE=21$ , calculate the lower bound obtained by deleting each of $A$ , $C$ and $D$ in turn, state the best lower bound, and combine it with the nearest neighbour tour from $B$ to trap the optimal tour length.
(9)
(Total for Question 1 is 9 marks)
2.
For the complete network on $A$ to $E$ with $AB=14$ , $AC=20$ , $AD=23$ , $AE=12$ , $BC=9$ , $BD=18$ , $BE=25$ , $CD=11$ , $CE=17$ , $DE=21$ , find the minimum spanning tree of the whole network and the upper bound obtained by doubling it. Compare that bound with the nearest neighbour tour from $A$ and comment.
(8)
(Total for Question 2 is 8 marks)
3.
Explain why deleting a vertex and adding the two shortest arcs at it always produces a valid lower bound for the classical travelling salesman problem, and explain why different deleted vertices can give different bounds.
(7)
(Total for Question 3 is 7 marks)
4.
A network has vertices $A$ to $E$ and arcs $AB=9$ , $AC=15$ , $BC=7$ , $BD=12$ , $CD=6$ , $CE=14$ , $DE=8$ , with no other direct connections. Using the complete network of shortest distances, apply the nearest neighbour algorithm from $C$ and find the lower bound obtained by deleting $A$ . State what the two results tell you.
(9)
(Total for Question 4 is 9 marks)
5.
In a travelling salesman problem the best lower bound found is $64$ and the best upper bound found is $67$ . Explain exactly what can and cannot be concluded about the optimal tour, and state what would have to happen for the optimal length to be determined by bounds alone.
(6)
(Total for Question 5 is 6 marks)

Answer key

Answers begin on a new printed page so the question pack can be completed without the solutions alongside it.

D1-3.1 · Algorithm for finding the shortest route around a network, travelling along every edge at least once and ending at the start vertex (the Route Inspection Algorithm).

Tier 1 · Easy

Mark scheme for D1-3.1 Tier 1 · Easy
Question	Scheme	Marks
1	Length $=84$ Every vertex has even order, so the network is Eulerian An Eulerian network has a closed trail using every arc exactly once, so nothing needs repeating	3
(3 marks)		3
Notes
A closed route covering every arc exists without repetition precisely when the network is connected and every vertex has even order. Here that condition holds, so the shortest such route is a single Eulerian circuit whose length is the total weight of the network, $84$ .
2	Orders: $A$ is $3$ , $B$ is $3$ , $C$ is $4$ , $D$ is $4$ , $E$ is $4$ , $F$ is $2$ The odd vertices are $A$ and $B$ Total weight $=8+5+9+6+7+4+11+12+10+3=75$ The shortest path from $A$ to $B$ is the arc $AB=8$ Route length $=75+8=83$	5
(5 marks)		5
Notes
Counting arcs at each vertex gives orders $3, 3, 4, 4, 4, 2$ , so only $A$ and $B$ are odd. With exactly two odd vertices there is only one pairing, and the shortest path between them must be repeated. The direct arc $AB=8$ beats $A$ to $C$ to $B$ at $5+6=11$ and every other route, so $8$ is repeated. The total weight is $75$ , giving a route of length $83$ .

Tier 2 · Standard

Mark scheme for D1-3.1 Tier 2 · Standard
Question	Scheme	Marks
1	Orders: $A$ is $3$ , $B$ is $3$ , $C$ is $4$ , $D$ is $4$ , $E$ is $3$ , $F$ is $3$ The odd vertices are $A$ , $B$ , $E$ and $F$ Total weight $=7+9+12+5+8+6+10+4+14+11=86$ Pairing $AB+EF=7+11=18$ Pairing $AF+BE=12+12=24$ Pairing $AE+BF=19+19=38$ The smallest repeat is $18$ , so the route length is $86+18=104$	7
(7 marks)		7
Notes
The orders are $A=3$ , $B=3$ , $C=4$ , $D=4$ , $E=3$ , $F=3$ , so four vertices are odd and three pairings must be tested. The shortest paths are $AB=7$ direct; $EF=11$ direct; $AF=12$ direct; $BE=8+4=12$ through $D$ ; $AE=7+8+4=19$ through $B$ and $D$ ; and $BF=7+12=19$ through $A$ . The pairing totals are $18$ , $24$ and $38$ , so the arcs on the shortest $AB$ and $EF$ paths are repeated, adding $18$ to the total weight of $86$ .
2	A closed route that repeats a set of arcs traverses the network as if those arcs were doubled The route exists only when every vertex has even order in the doubled network Repeating a path raises the order of its two endpoints by $1$ and each internal vertex by $2$ So the repeated arcs must form paths whose endpoints are exactly the odd vertices, taken in pairs With $4$ odd vertices there are $3$ pairings With $6$ odd vertices there are $15$ pairings	5
(5 marks)		5
Notes
Doubling an arc adds one to the order of each endpoint, so repeating a whole path changes the parity only at its two ends. To make every order even, the repeated arcs must therefore decompose into paths that pair off the odd vertices and nothing else. The number of ways to split $2m$ objects into pairs is $1\times3\times5\times\cdots\times(2m-1)$ , giving $1\times3=3$ pairings for four odd vertices and $1\times3\times5=15$ for six.
3	Orders: $A$ is $3$ , $B$ is $3$ , $C$ is $4$ , $D$ is $4$ , $E$ is $4$ , $F$ is $3$ , $G$ is $3$ The odd vertices are $A$ , $B$ , $F$ and $G$ Total weight $=103$ Pairing $AB+FG=6+12=18$ Pairing $AG+BF=9+15=24$ Pairing $AF+BG=21+15=36$ The smallest repeat is $18$ , so the route length is $103+18=121$	7
(7 marks)		7
Notes
The orders are $3, 3, 4, 4, 4, 3, 3$ , so $A$ , $B$ , $F$ , $G$ are odd. The arcs total $6+11+9+4+13+7+8+5+10+3+15+12=103$ . The required shortest paths are $AB=6$ ; $FG=12$ ; $AG=9$ ; $BF=4+8+3=15$ through $C$ and $E$ ; $AF=9+12=21$ through $G$ , which is tied by $6+4+8+3=21$ through $B$ , $C$ and $E$ , so $21$ ; and $BG=6+9=15$ through $A$ . The pairing totals are $18$ , $24$ and $36$ , so $18$ is repeated on top of $103$ .

Tier 3 · Hard

Mark scheme for D1-3.1 Tier 3 · Hard
Question	Scheme	Marks
1	The odd vertices are $A$ , $B$ , $E$ , $F$ and the total weight is $86$ The start and finish must be two of the odd vertices, and the other two must be paired and repeated Start and finish $A$ , $B$ : repeat $EF=11$ , length $97$ Start and finish $A$ , $E$ : repeat $BF=19$ , length $105$ Start and finish $A$ , $F$ : repeat $BE=12$ , length $98$ Start and finish $B$ , $E$ : repeat $AF=12$ , length $98$ Start and finish $B$ , $F$ : repeat $AE=19$ , length $105$ Start and finish $E$ , $F$ : repeat $AB=7$ , length $93$ The shortest is $93$ , starting at $E$ and finishing at $F$ , or the reverse	8
(8 marks)		8
Notes
An open route covering every arc exists when exactly two vertices have odd order, and those two are the start and finish. Two of the four odd vertices may therefore be left unpaired, and the shortest paths pairing the remaining two must be repeated. The six shortest paths are $AB=7$ , $AE=19$ , $AF=12$ , $BE=12$ , $BF=19$ and $EF=11$ . Leaving $E$ and $F$ as the endpoints requires only $AB=7$ to be repeated, which is the smallest of the six values, so the route length is $86+7=93$ and no other choice of endpoints does better.
2	The repeat total is $184-148=36$ Pairing $PQ+RS=17+14=31$ Pairing $PS+QR=21+19=40$ Pairing $PR+QS=x+26$ The repeat is the smallest of $31$ , $40$ and $x+26$ , which is at most $31$ for every $x>0$ So the route length is at most $148+31=179$ , and never $184$ No value of $x$ makes the claim true For $x\geqslant5$ the shortest closed route has length $179$ For $0<x<5$ the shortest closed route has length $174+x$	7
(7 marks)		7
Notes
The claim requires a repeat total of $184-148=36$ , and the route length is the network weight plus the smallest of the three pairing totals. Two of those totals are fixed: $PQ+RS=17+14=31$ and $PS+QR=21+19=40$ . Since $31<36$ , the minimum of the three is at most $31$ whatever $x$ is, so the route can never be as long as $184$ and the claim fails for every $x$ . The third total, $PR+QS=x+26$ , beats $31$ exactly when $x<5$ , so the shortest route is $148+(x+26)=174+x$ for $0<x<5$ and $148+31=179$ for $x\geqslant5$ .
3	Without the new road the best pairing is $AB+FG=6+12=18$ , giving $103+18=121$ kilometres The new road makes the network weight $103+4=107$ kilometres The new road makes the orders of $A$ and $F$ even, so the odd vertices become $B$ and $G$ only The shortest path from $B$ to $G$ is now $\min(15, 6+4+12)=\min(15, 22)$ , so $BA$ then $AG$ still gives $6+9=15$ Repeat $BG=15$ , giving $107+15=122$ kilometres The route is $1$ kilometre longer, so the new road does not shorten it	8
(8 marks)		8
Notes
As it stands the lorry repeats the shortest paths $AB$ and $FG$ , a total of $18$ , for a route of $121$ kilometres. Building $AF$ adds $4$ to the network that must be covered and changes the parity of $A$ and $F$ , leaving only $B$ and $G$ odd. The single pairing then required is $B$ to $G$ , whose shortest path is $BA$ followed by $AG$ , of length $15$ ; going $B$ to $A$ to $F$ to $G$ costs $6+4+12=22$ and is longer. The new route is $107+15=122$ kilometres, which exceeds $121$ , so the council's road makes the gritting round one kilometre longer even though it shortens the direct trip from $A$ to $F$ .
4	The first odd vertex can be paired with any of the other $5$ The next unpaired vertex can be paired with any of the remaining $3$ The last two must pair together The number of pairings is $5\times3\times1=15$ The specification limits inspection to networks with at most four odd vertices For six odd vertices the examiner must restrict which pairings are allowed, for example by naming vertices that must be the route's endpoints or arcs that may not be repeated	6
(6 marks)		6
Notes
Counting perfect pairings of $2m$ objects gives the double factorial $(2m-1)!!$ , which is $5\times3\times1=15$ when $m=3$ . Testing fifteen pairings by inspection is beyond what the specification asks, since it states that the network will contain at most four odd nodes. When more odd nodes appear, additional information must cut the list down: typically the route is allowed to start and finish at two named odd vertices, which removes them from the pairing, or a subset of arcs is declared unavailable for repetition.
5	Total weight $=67+k$ The route repeats the shortest path from $A$ to $B$ Direct route $AB$ has length $k$ The best indirect route is $A$ to $C$ to $B$ , of length $5+6=11$ Shortest path $=\min(k, 11)$ For $0<k\leqslant11$ the route length is $67+k+k=67+2k$ For $k>11$ the route length is $67+k+11=78+k$	8
(8 marks)		8
Notes
The arcs other than $AB$ total $5+9+6+7+4+11+12+10+3=67$ , so the network weight is $67+k$ . Only $A$ and $B$ are odd, so the shortest $A$ to $B$ path is repeated. The candidates are the arc $AB$ itself, of length $k$ , and the path $ACB$ , of length $11$ ; every other route is longer, since $A$ to $D$ to $C$ to $B$ costs $9+4+6=19$ . The repeat is therefore $\min(k, 11)$ , giving $67+2k$ while $k\leqslant11$ and $78+k$ once $k>11$ , with the two expressions agreeing at $k=11$ .

D1-3.2 · The practical and classical Travelling Salesman problems. Determination of upper and lower bounds using minimum spanning tree methods. The nearest neighbour algorithm.

Tier 1 · Easy

Mark scheme for D1-3.2 Tier 1 · Easy
Question	Scheme	Marks
1	In the classical problem each vertex is visited exactly once In the practical problem a vertex may be visited more than once The practical problem is converted by replacing the network with the complete network of shortest distances between every pair of vertices	3
(3 marks)		3
Notes
The classical problem asks for a Hamiltonian cycle of least weight, so no vertex may be revisited; the practical problem allows a tour to pass back through a vertex, which is what a real delivery round often needs. Replacing each pair of vertices by the shortest path between them produces a complete network in which any classical tour corresponds to a practical tour of the same length, so the two problems agree on the converted network.
2	From $B$ the nearest is $C$ at $9$ From $C$ the nearest unvisited is $D$ at $11$ From $D$ the nearest unvisited is $E$ at $21$ From $E$ the only one left is $A$ at $12$ , then $A$ back to $B$ at $14$ Tour $BCDEAB$ of length $9+11+21+12+14=67$ Upper bound $=67$	4
(4 marks)		4
Notes
Starting at $B$ , the arcs available are $BA=14$ , $BC=9$ , $BD=18$ , $BE=25$ , so $C$ is chosen. From $C$ the unvisited options are $CA=20$ , $CD=11$ , $CE=17$ , so $D$ is chosen. From $D$ the unvisited options are $DA=23$ and $DE=21$ , so $E$ is chosen; then $A$ is forced, and the tour closes with $AB=14$ . Any actual tour is a candidate solution, so its length $67$ is an upper bound for the optimal tour.

Tier 2 · Standard

Mark scheme for D1-3.2 Tier 2 · Standard
Question	Scheme	Marks
1	From $A$ the nearest is $E$ at $12$ From $E$ the nearest unvisited is $C$ at $17$ From $C$ the nearest unvisited is $B$ at $9$ From $B$ the only one left is $D$ at $18$ , then $D$ back to $A$ at $23$ Tour $AECBDA$ of length $12+17+9+18+23=79$ The bound is poor, because the greedy choices leave the two longest arcs $BD$ and $DA$ to the end	5
(5 marks)		5
Notes
Nearest neighbour from $A$ takes $AE=12$ , then $EC=17$ since $EB=25$ and $ED=21$ are longer, then $CB=9$ , then the forced $BD=18$ and the forced return $DA=23$ . The total is $79$ . The algorithm never looks ahead, so cheap early arcs can strand a vertex whose remaining connections are expensive; here $D$ is left until last and both of its used arcs are long, which is why $79$ is a much weaker bound than a tour found from another start vertex.
2	Deleting $C$ leaves $A$ , $B$ , $D$ , $E$ with arcs $AB=14$ , $AD=23$ , $AE=12$ , $BD=18$ , $BE=25$ , $DE=21$ Residual minimum spanning tree: $AE=12$ , $AB=14$ , $BD=18$ Residual weight $=44$ The two shortest arcs at $C$ are $BC=9$ and $CD=11$ Lower bound $=44+9+11=64$	5
(5 marks)		5
Notes
Removing $C$ leaves a complete network on four vertices. Kruskal's algorithm on it takes $AE=12$ , then $AB=14$ , then $BD=18$ , rejecting $DE=21$ and the rest as they would close cycles or are longer, giving a residual tree of weight $44$ . The two shortest arcs meeting $C$ are $BC=9$ and $CD=11$ . Any tour enters and leaves $C$ once, using two arcs at $C$ costing at least $9+11$ , and the rest of the tour is a spanning path of the remaining vertices, which is at least as heavy as their minimum spanning tree. The bound is therefore $44+9+11=64$ .
3	$AB=9$ , $AC=15$ , $AD=21$ , $AE=29$ $BC=7$ , $BD=12$ , $BE=20$ $CD=6$ , $CE=14$ $DE=8$ $AD$ uses $A$ to $C$ to $D$ or $A$ to $B$ to $D$ , both of length $21$ $AE$ uses $A$ to $C$ to $E$ or $A$ to $C$ to $D$ to $E$ , both of length $29$ $BE$ uses $B$ to $D$ to $E$ , of length $12+8=20$	6
(6 marks)		6
Notes
The direct arcs are already shortest for $AB$ , $BC$ , $BD$ , $CD$ , $CE$ and $DE$ , and $AC=15$ beats $A$ to $B$ to $C$ at $9+7=16$ . For the missing pairs, $A$ to $D$ costs $15+6=21$ through $C$ and also $9+12=21$ through $B$ ; $A$ to $E$ costs $15+14=29$ through $C$ and $21+8=29$ through $C$ and $D$ ; and $B$ to $E$ costs $12+8=20$ through $D$ , beating $7+14=21$ through $C$ . Collecting these gives the complete network of shortest distances.

Tier 3 · Hard

Mark scheme for D1-3.2 Tier 3 · Hard
Question	Scheme	Marks
1	Deleting $A$ : residual tree $BC=9$ , $CD=11$ , $CE=17$ , weight $37$ ; two shortest at $A$ are $12$ and $14$ ; bound $=63$ Deleting $C$ : residual tree $AE=12$ , $AB=14$ , $BD=18$ , weight $44$ ; two shortest at $C$ are $9$ and $11$ ; bound $=64$ Deleting $D$ : residual tree $BC=9$ , $AE=12$ , $AB=14$ , weight $35$ ; two shortest at $D$ are $11$ and $18$ ; bound $=64$ The best lower bound is $64$ The nearest neighbour tour from $B$ is $BCDEAB$ of length $67$ $64\leqslant T\leqslant67$ , where $T$ is the optimal tour length	9
(9 marks)		9
Notes
For each deletion, run Kruskal on the four remaining vertices and add the two cheapest arcs at the deleted vertex. Deleting $A$ leaves $B$ , $C$ , $D$ , $E$ with tree $BC=9$ , $CD=11$ , $CE=17$ of weight $37$ , and $AE=12$ , $AB=14$ are the two shortest at $A$ , giving $63$ . Deleting $C$ gives the tree $AE=12$ , $AB=14$ , $BD=18$ of weight $44$ and the arcs $BC=9$ , $CD=11$ , giving $64$ . Deleting $D$ gives the tree $BC=9$ , $AE=12$ , $AB=14$ of weight $35$ and the arcs $CD=11$ , $BD=18$ , giving $64$ . Every one of these is a valid lower bound, so the largest, $64$ , is the best. The nearest neighbour tour from $B$ is a genuine tour of length $67$ , so the optimal length lies between $64$ and $67$ inclusive.
2	Minimum spanning tree: $BC=9$ , $CD=11$ , $AE=12$ , $AB=14$ Weight $=46$ Upper bound by doubling $=2\times46=92$ Nearest neighbour tour from $A$ is $AECBDA$ of length $79$ The nearest neighbour bound of $79$ is better, because it is smaller A smaller upper bound is more useful, since it narrows the interval containing the optimal tour	8
(8 marks)		8
Notes
Kruskal on the whole network takes $BC=9$ , $CD=11$ , $AE=12$ and $AB=14$ , rejecting $CE=17$ and $BD=18$ as they would close cycles, for a tree of weight $46$ . Walking out and back along every arc of the tree gives a closed walk of length $92$ that visits every vertex, so $92$ is an upper bound. The nearest neighbour tour from $A$ has length $79$ . Both are valid, but an upper bound is only as good as it is small, so $79$ is the one to quote; the doubling bound is usually weak until short cuts are used to skip repeated vertices.
3	Any tour visits the deleted vertex $X$ exactly once, arriving on one arc and leaving on another Those two arcs cost at least the sum of the two shortest arcs at $X$ Removing $X$ and its two arcs from the tour leaves a path through every other vertex A path through every other vertex is a spanning tree of them, so it weighs at least the residual minimum spanning tree Adding the two parts gives a quantity that no tour can fall below, so it is a lower bound The bound is only attained when the residual tree happens to be a path and both cheapest arcs at $X$ are usable Different choices of $X$ relax different parts of the problem, so the bounds differ and the largest is the most useful	7
(7 marks)		7
Notes
Split any tour at the deleted vertex $X$ . The tour uses exactly two arcs at $X$ , whose total is at least the sum of the two smallest weights at $X$ , and the remainder of the tour is a Hamiltonian path on the other vertices, which is a particular spanning tree of them and therefore weighs at least the residual minimum spanning tree. Adding these two lower estimates gives a number that every tour exceeds or equals. The estimate is loose whenever the residual minimum spanning tree branches, since a genuine tour needs a path, so the amount of slack depends on which vertex was deleted; taking the maximum over all deletions therefore gives the strongest bound available by this method.
4	Shortest distances: $AB=9$ , $AC=15$ , $AD=21$ , $AE=29$ , $BC=7$ , $BD=12$ , $BE=20$ , $CD=6$ , $CE=14$ , $DE=8$ From $C$ the nearest is $D$ at $6$ , then $E$ at $8$ , then $B$ at $20$ , then $A$ at $9$ , then $A$ back to $C$ at $15$ Nearest neighbour tour $CDEBAC$ of length $6+8+20+9+15=58$ Deleting $A$ leaves $B$ , $C$ , $D$ , $E$ ; residual minimum spanning tree $CD=6$ , $BC=7$ , $DE=8$ , weight $21$ The two shortest arcs at $A$ are $AB=9$ and $AC=15$ Lower bound $=21+9+15=45$ The optimal practical tour length $T$ satisfies $45\leqslant T\leqslant58$	9
(9 marks)		9
Notes
The missing distances are $AD=21$ through $C$ or $B$ , $AE=29$ through $C$ , and $BE=20$ through $D$ . Nearest neighbour from $C$ takes $CD=6$ , then $DE=8$ , then $EB=20$ since $EA=29$ is longer, then the forced $BA=9$ and the closing $AC=15$ , giving $58$ . Deleting $A$ leaves the complete network on $B$ , $C$ , $D$ , $E$ , whose minimum spanning tree by Kruskal is $CD=6$ , $BC=7$ , $DE=8$ of weight $21$ , and the two shortest arcs at $A$ are $9$ and $15$ , so the bound is $45$ . The optimal tour therefore lies between $45$ and $58$ ; the two do not meet, so this pair of calculations does not identify the optimum.
5	The optimal tour length $T$ satisfies $64\leqslant T\leqslant67$ The upper bound $67$ comes from an actual tour, so a tour of length $67$ is known to exist The lower bound $64$ need not be achievable, since it comes from a relaxed problem It cannot be concluded that the optimum is $64$ , nor that any particular tour is optimal The possible values of $T$ are $64$ , $65$ , $66$ and $67$ if all arc weights are integers The optimum is settled only when an upper bound and a lower bound coincide	6
(6 marks)		6
Notes
An upper bound is the length of a tour that has actually been constructed, so it is attainable; a lower bound comes from a relaxation in which the tour condition has been weakened, so it may be strictly below every real tour. Together they confine the optimum to the interval $[64, 67]$ , and with integer weights that leaves four candidate values. Nothing in the pair of numbers identifies which, so the only way to conclude a value from bounds alone is to find a tour whose length equals a valid lower bound, at which point both bounds are tight and that tour is optimal.