Questions on route inspection

Question 1

Explain why a network with odd nodes cannot be walked using every edge exactly once and returning to the start.

Accepted Answer

Every visit to a node uses one edge to arrive and one to leave, so a closed trail uses the edges at each node in pairs. A node of odd order would have an edge left over with no partner, so no such trail exists unless every node has even order. B1 for the edges at each node being used in pairs, B1 for the odd node leaving one unpaired.

Question 2

Every vertex of a connected network has even order and the edges total 74. Write down the length of the shortest closed route that uses every edge at least once, and state which edges are repeated.

Accepted Answer

The route has length 74, the total weight of the network, and no edge is repeated. B1 for 74, B1 for nothing repeated.
With no odd vertices the network is Eulerian, so a closed trail exists that uses every edge exactly once, and no repetition can improve on that.

Question 3

A network of total weight 90 has odd vertices P, Q, R and S, with shortest paths PQ 11, PR 7, PS 14, QR 13, QS 8 and RS 12. List the three pairings with their costs, and find the length of the shortest closed route that uses every edge at least once.

Accepted Answer

Pairings: PQ with RS costs 11 + 12 = 23; PR with QS costs 7 + 8 = 15; PS with QR costs 14 + 13 = 27. B1 for all three.
The cheapest is 15, so the shortest closed route is 90 + 15 = 105. M1 for adding the cheapest pairing to the total weight, A1 for 105.
The edges of the P to R path and of the Q to S path are the ones walked twice; every other edge is walked once, and the route may start anywhere.

Question 4

The odd nodes of a network are A, B, D and E, with shortest paths AB 5, AD 9, AE 13, BD 7, BE 9, DE 9. List the three pairings with their costs.

Accepted Answer

AB with DE: 5 + 9 = 14. AD with BE: 9 + 9 = 18. AE with BD: 13 + 7 = 20. B1 B1 B1 for the three pairings with their costs. Four odd nodes always give exactly three pairings, and the specification caps the number at four for that reason.

Question 5

The nine edges of that network total 55. Find the length of the shortest closed route using every edge at least once, and name the repeated edges, given that the shortest D to E path runs through C.

Accepted Answer

The cheapest pairing costs 14, so the route is 55 + 14 = 69. The repeated stretches are AB and the shortest D to E path, which is DC and CE. M1 for choosing the cheapest pairing, A1 for 14, A1 for 69, B1 for the repeated edges. Every other edge is walked exactly once, and the route may start anywhere.

Question 6

For the same network, find the shortest route that need not return to the start, and say where it begins and ends.

Accepted Answer

An open route leaves two odd nodes unpaired, one at each end. To minimise the repetition, pair the two odd nodes with the cheapest connection and leave the others: pairing A with B costs 5, leaving D and E as the endpoints. The route is 55 + 5 = 60, starting at D and finishing at E, or the other way round. M1 for leaving two odd nodes unpaired, A1 for the cheapest pairing of 5, A1 for 60, B1 for the two endpoints.

Question 7

Explain why the pairings use shortest paths between odd nodes rather than single edges, and why repeating an edge between two even nodes never helps.

Accepted Answer

Two odd nodes may not be joined directly, and even when they are, a route through other nodes may be shorter. Repeating the edges of a shortest path raises the order of the two odd ends by one each and raises the intermediate nodes by two, leaving them even. Repeating an edge between two even nodes would make both odd, adding to the problem instead of solving it. B1 for a direct edge not always existing, B1 for a path through other nodes possibly being shorter, B1 for repeating an edge between even nodes making both odd.

Question 8

Explain why a connected network must have an even number of odd nodes. Given that 2n odd nodes can be paired up in 1 × 3 × 5 × … × (2n − 1) ways, find how many pairings would have to be compared if a network had six odd nodes.

Accepted Answer

Every edge meets two nodes, so adding the orders of all the nodes counts each edge twice and the total is 2 × (number of edges), which is even. The even-order nodes contribute an even amount to that total, so the odd-order nodes must contribute an even amount between them, and an even sum of odd numbers needs an even count of them.
With six odd nodes, 2n = 6 and n = 3, so the count is 1 × 3 × 5 = 15 pairings. Four odd nodes give 1 × 3 = 3, and eight would give 1 × 3 × 5 × 7 = 105, which is why the specification restricts route inspection questions to at most four odd nodes.
B1 for the orders totalling twice the number of edges, B1 for an even sum of odd numbers requiring an even count, M1 for 1 × 3 × 5, A1 for 15.
Take the first odd node: it can be partnered with any of the other 5, leaving 4 nodes; the first of those can be partnered with any of the remaining 3, leaving 2, which have only 1 pairing between them. That is 5 × 3 × 1, written the other way round above.

Question 9

A connected network has vertices P, Q, R, S, T, U of orders 3, 4, 3, 5, 2 and 3 respectively. Identify the odd vertices, list every possible pairing of them, and state how many pairings would have to be listed if the network had six odd vertices instead.

Accepted Answer

The orders total 3 + 4 + 3 + 5 + 2 + 3 = 20, so the network has 10 edges, and the odd vertices are P, R, S and U. B1.
Build the pairings by partnering P with each of the other three in turn, the remaining two then having only one partner between them: PR with SU, PS with RU, PU with RS. M1 for partnering one vertex with each of the others, A1 for all three pairings.
With six odd vertices the count is 1 × 3 × 5 = 15. B1.

Question 10

A network has vertices P, Q, R, S, T, U and edges PQ 14, PR 8, PU 12, QR 4, QS 9, RS 6, RT 7, ST 5, TU 3, SU 11. Find the length of the shortest closed route that uses every edge at least once, and state which edges are repeated.

Accepted Answer

Orders: P 3, Q 3, R 4, S 4, T 3, U 3, so the odd vertices are P, Q, T and U. The edges total 14 + 8 + 12 + 4 + 9 + 6 + 7 + 5 + 3 + 11 = 79. B1 for the odd vertices, B1 for 79.
Shortest paths between them: P to Q = 12 by P, R, Q, which beats the direct edge of 14; T to U = 3 along the edge; P to T = 15 by P, R, T or by P, U, T; P to U = 12 along the edge; Q to T = 11 by Q, R, T; Q to U = 14 by Q, R, T, U. M1 for the shortest paths, with the P to Q path found.
Pairings: PQ + TU = 12 + 3 = 15; PT + QU = 15 + 14 = 29; PU + QT = 12 + 11 = 23. A1 for the three pairings.
The cheapest is 15, so the shortest closed route is 79 + 15 = 94, and the repeated edges are PR, RQ and TU. A1.
Taking the direct PQ of 14 would give a pairing of 17 and a route of 96, and would name the wrong repeated edge as well. The repeated edges are the edges of the path, not the pair of vertices.

Question 11

A network has vertices A to F and edges AB 7, AC 5, AE 8, BC 4, BD 7, CD 6, CE 3, CF 10, DE 5, DF 8, EF 5. Find the length of the shortest closed route that traverses every edge at least once, and state which edges are repeated.

Accepted Answer

Degrees: A 3, B 3, C 5, D 4, E 4, F 3. The odd vertices are A, B, C and F, and the edges total 68.
Shortest paths between them: AB = 7 along the edge; AC = 5; BC = 4; AF = 13 by A, C, E, F; BF = 12 by B, C, E, F; and CF = 8 by C, E, F, which beats the direct edge CF of 10.
Pairings: AB + CF = 7 + 8 = 15; AC + BF = 5 + 12 = 17; AF + BC = 13 + 4 = 17.
The cheapest is 15, so the shortest closed route has length 68 + 15 = 83, and the repeated edges are AB, CE and EF.
B1 for the four odd vertices, B1 for the total of 68, M1 for the shortest paths between odd vertices, A1 for the C to F path of 8, M1 for the three pairings, A1 for 15, A1 for 83, A1 for the repeated edges. The trap is the pair C and F. Taking the direct edge of 10 gives a pairing of 17 and a route of 85, because 10 is not the shortest distance from C to F.

Question 12

A network has vertices A to G and edges AB 7, AC 9, AD 5, BC 4, BE 8, CD 3, CE 7, CF 11, DF 8, EF 5, EG 6, FG 4. Find the length of the shortest closed route that uses every edge at least once, and state which edges are repeated.

Accepted Answer

Orders: A 3, B 3, C 5, D 3, E 4, F 4, G 2, so the odd vertices are A, B, C and D. The edges total 77.
Shortest paths between the odd vertices: AB = 7 along the edge, AD = 5, BC = 4, CD = 3, BD = 7 through C, and AC = 8 through D, which beats the direct edge of 9.
Pairings: AD + BC = 5 + 4 = 9; AB + CD = 7 + 3 = 10; AC + BD = 8 + 7 = 15.
The cheapest is 9, so the shortest closed route is 77 + 9 = 86, and the repeated edges are AD and BC.
B1 for the four odd vertices, B1 for the total of 77, M1 for the three pairings, A1 for their three costs, A1 for 86, B1 for the repeated edges.
Taking the direct 9 makes that pairing 16 rather than 15, which does not change the winner here but gives the wrong pairing cost.

Question 13

For the same network, a route must use every edge at least once, starting at A and finishing at G. Find its shortest possible length, state which edges are repeated, and compare the answer with the closed route.

Accepted Answer

A trail that starts at A and finishes at G has odd order at exactly those two vertices and even order everywhere else, once the repeated edges are counted in. A is already odd and stays odd. B, C and D are odd and must be made even, and G has order 2 and must be made odd. So the four vertices to pair are B, C, D and G, not the four odd ones.
Shortest paths: BC = 4, BD = 7 through C, CD = 3, DG = 12 by D, F, G, CG = 13 by C, E, G, and BG = 14 by B, E, G.
Pairings: BC + DG = 4 + 12 = 16; BG + CD = 14 + 3 = 17; BD + CG = 7 + 13 = 20.
The cheapest is 16, so the route is 77 + 16 = 93, repeating BC, DF and FG.
That is 7 longer than the closed route of 86. Dropping the return to the start usually saves, but only if the two ends are free to be chosen: here G sits on the far side of the network with only two edges reaching it, and forcing the route to end there costs more than returning to A.
M1 for deciding which vertices must change order, A1 for B, C, D and G, M1 for the three pairings, A1 for 16, A1 for 93, B1 for the repeated edges, B1 for the comparison.

Question 14

A network has vertices P, Q, R, S, T and edges PQ 6, PR 9, PS 4, QR 5, QT 7, RS 3, RT 8, ST 10. Find the length of the shortest closed route that uses every edge at least once and state which edges are repeated. The road PS is then resurfaced and its weight rises from 4 to 15; find the new answer.

Accepted Answer

Orders: P 3, Q 3, R 4, S 3, T 3, so the odd vertices are P, Q, S and T. The edges total 6 + 9 + 4 + 5 + 7 + 3 + 8 + 10 = 52. B1 for the odd vertices, B1 for 52.
Shortest paths between them: PQ = 6 along the edge, PS = 4, QT = 7, QS = 8 by Q, R, S, ST = 10, and PT = 13 by P, Q, T. M1 for the shortest paths and the three pairings.
Pairings: PS + QT = 4 + 7 = 11; PQ + ST = 6 + 10 = 16; PT + QS = 13 + 8 = 21. The cheapest is 11, so the route is 52 + 11 = 63, repeating PS and QT. A1.
With PS at 15 the edges total 52 − 4 + 15 = 63. The shortest P to S distance is no longer the direct edge: P, R, S costs 9 + 3 = 12, which beats 15. Every other shortest path is unchanged, since none of them used PS. M1 for reworking the distances.
New pairings: PS + QT = 12 + 7 = 19; PQ + ST = 6 + 10 = 16; PT + QS = 21. The cheapest is now 16, so the route is 63 + 16 = 79, repeating PQ and ST. A1.

Question 15

A gritting lorry must drive along every road of a network at least once. The roads total 96 km and the odd junctions are P, Q, R and S, with shortest distances PQ 7, PR 12, PS 9, QR 8, QS 15, RS 6. Find the shortest round that starts and finishes at the depot at P. The lorry may instead finish at a second depot at any one of the other junctions; find the shortest such round and where it ends. State one assumption the network model makes that a real gritting round would break.

Accepted Answer

Pairings: PQ + RS = 7 + 6 = 13; PR + QS = 12 + 15 = 27; PS + QR = 9 + 8 = 17. M1 for the three pairings.
The cheapest is 13, so the closed round is 96 + 13 = 109 km. A1.
A round that starts at P and finishes elsewhere leaves two odd junctions unpaired, one at each end, and P must be one of them. So pair the other two and leave P with whichever is left: leaving P and Q pairs R with S at 6, giving 102; leaving P and R pairs Q with S at 15, giving 111; leaving P and S pairs Q with R at 8, giving 104. M1 for leaving P and one other unpaired.
The shortest is 102 km, finishing at Q, which is 7 km less than returning to P. A1.
One assumption the model makes: every road may be driven in either direction, so no road is one-way; or the lorry can turn at any junction with no cost in distance or time; or the lorry never has to break off to refill with grit. B1 for any one of these.