Route inspection: four odd vertices

With four odd vertices you must decide how to pair them up. D1 expects you to list every pairing and compare totals.

All three pairings

Four odd vertices W, X, Y, Z can be paired in exactly three ways: WX and YZ, WY and XZ, WZ and XY. For each pairing find the shortest path between each pair (by inspection, unless Dijkstra is asked for) and add them.

Choosing

Repeat the paths of the pairing with the smallest total. Shortest route = total weight of network + that smallest total. Show all three totals: marks are given for considering every pairing.

Different start and finish

If the route may start and finish at different vertices, choose two of the odd vertices to be the start and finish. The other two must be joined by a repeated shortest path. Choose the pair with the shortest connecting path to repeat, so start and finish at the other two.

Changes to the problem

Questions may add an edge, fix the start at a particular vertex, or ask which vertices a route passes through most often. Recount the odd vertices after any change.

Worked example

Network N has total weight 99. Find the shortest closed route covering every edge.

Odd vertices: A, B, E, F
AB and EF: 7 + 3 = 10
AE and BF: 16 + 12 = 28
AF and BE: 19 + 9 = 28
Smallest: AB and EF = 10; length = 99 + 10 = 109

Answer: 109

Key idea: List all three pairings of the four odd vertices, add shortest paths for each, repeat the smallest; total weight + that amount.

Check yourself

Which vertices of network N have odd degree?
- A, B, C, D
- B, E, F, G
- C, D, E, G
- A, B, E, F
Show answer
A, B, E, F. Degrees: A 3, B 3, C 4, D 4, E 5, F 3, G 2.
How many different pairings are there for four odd vertices?
Show answer
3. WX and YZ, WY and XZ, WZ and XY: three pairings.
Find the smallest total of repeated edges for network N, considering all pairings of the odd vertices.
Show answer
10. AB and EF = 10; AE and BF = 28; AF and BE = 28. Smallest 10.
Find the length of the shortest route that covers every edge of network N and returns to the start.
Show answer
109. 99 + 10 = 109.
In network N, what is the length of the shortest path from A to E (used in the pairing AE and BF)?
Show answer
16. A to C to B to E is 20; A to B to E is 16; A to C to D to E is 17; A to D to E is 18. So 16.
The route around network N may start and finish at different vertices. Where should it start and finish to be as short as possible?
- Start at A and finish at B
- Start at A and finish at F
- Start at A and finish at E
- Start at B and finish at F
Show answer
Start at A and finish at B. Repeat the shortest path between two odd vertices and start and finish at the other two. Shortest paths: AB = 7; AE = 16; AF = 19; BE = 9; BF = 12; EF = 3. Smallest is EF = 3, so start and finish at A and B.
Why must all three pairings be shown in a four odd vertex route inspection answer?
- Because every pairing must be repeated
- Because the algorithm picks the pairing at random
- To show that the chosen pairing really gives the smallest total
- To find the Eulerian route
Show answer
To show that the chosen pairing really gives the smallest total. Only by comparing every pairing can you justify that your repeated edges are the least possible.

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.