The Route Inspection Problem Revision Notes for AQA A-Level Further Maths

The Route Inspection Problem

Introduction

The route inspection problem is a classic graph theory challenge also known as the Chinese postman problem. It was originally discussed by the Chinese mathematician Mei-ko Kwan.

Problem definition: For a given network, find the shortest route that travels at least once along every arc and returns to the starting point.

infoNote

The key idea is that you want to travel just once along each arc if possible. This is achievable when the network has specific properties that we'll explore in this chapter.

Eulerian networks and traversability

A network is called Eulerian (or traversable) when you can travel along every arc exactly once and return to your starting point.

chatImportant

Key condition: If all nodes in the network have even degree, then the network is traversable. The total distance travelled equals the sum of all the arc weights.

What is the degree of a node?

The degree of a node is the number of arcs connected to it. When checking if nodes are even or odd, count how many arcs meet at that node.

infoNote

Counting degrees:

Each arc connected to a node contributes 1 to that node's degree
If an arc forms a loop (starts and ends at the same node), it contributes 2 to that node's degree
A node with degree 4 has exactly 4 arcs connected to it

Why do we need even nodes?

Each time you visit a node during your route, you use one arc to enter and one arc to leave. This means you use arcs in pairs at each node. If a node has odd degree, you cannot use all its arcs in pairs without travelling along at least one arc twice.

chatImportant

The pairing principle: At every node you visit (except possibly the start/finish), arcs must be used in pairs - one to enter, one to leave. This is why even-degree nodes work perfectly for traversable routes, while odd-degree nodes force you to repeat some arcs.

When networks are not Eulerian

If there are nodes of odd degree, you must repeat some arcs to complete the route. The route inspection problem then becomes:

Which arcs must be repeated to complete the route as efficiently as possible?

Repeating an arc is equivalent to adding an extra arc to the network with the same weight. Your goal is to choose which arcs to repeat so that all nodes become even and the network becomes traversable, whilst keeping the total extra distance as small as possible.

Always an even number of odd nodes

infoNote

Mathematical fact: Every network always has an even number of nodes with odd degree. This is because the sum of all degrees equals twice the number of arcs (each arc contributes 1 to the degree at both its endpoints). Since this sum is even, there must be an even number of odd-degree nodes.

When there are more than two odd nodes, you must pair them together. The best pairing minimises the total weight of the shortest routes between the paired nodes.

The route inspection algorithm

Follow these five steps to solve the route inspection problem:

Step 1: Identify the odd nodes.

List all nodes and count the degree of each. Mark which nodes have odd degree.

Step 2: List all possible pairings of the odd nodes.

If there are four odd nodes (A, B, C, D), the possible pairings are:

A with B, and C with D
A with C, and B with D
A with D, and B with C

Step 3: For each pairing, find the shortest routes between paired nodes and calculate the total weight of those routes.

Use inspection or a shortest path algorithm to find the shortest distance between each pair. Add these distances together to get the total for that pairing.

Step 4: Choose the pairing with the smallest total.

This pairing gives you the minimum extra distance needed.

Step 5: Repeat the shortest route arcs.

The arcs along the shortest routes for your chosen pairing must be travelled twice. These are the arcs you repeat to make all nodes even.

Calculating the total route length

$\text{Total route length} = (\text{sum of all original arc weights}) + (\text{sum of extra arc weights})$

The extra arc weights come from the shortest routes you identified in your chosen pairing.

Worked example 1: basic route inspection

lightbulbExample

Worked Example: Basic Route Inspection

Consider a network with vertices A, B, C, D forming a quadrilateral with diagonals. The arc weights are:

AB = 12, AC = 10, AD = 8
BC = 6, BD = 7, CD = 15
Diagonal arcs: 9 crossing

The sum of all arc weights is 67.

Solution:

Step 1: Check the degrees

A: degree 3 (odd)
B: degree 3 (odd)
C: degree 3 (odd)
D: degree 3 (odd)

All four nodes have odd degree.

Step 2: List pairings

There are three possible pairings:

Pairing 1: A with B, C with D
Pairing 2: A with C, B with D
Pairing 3: A with D, B with C

Step 3: Find shortest routes for each pairing

For this simple network, we need to identify which route from C to D is shortest. Looking at the network:

Direct route CD = 15
Route CBD = 6 + 7 = 13 (shorter)

If we pair C with D, we must use route CBD with length 13.

After checking all pairings (working shown in detail in exam), the best approach for this specific example is to identify which two nodes to pair based on the shortest connection.

If C and D are paired (both odd), the shortest route between them is C→B→D with length 6 + 7 = 13.

Step 4: The arcs CB and BD must be repeated.

Step 5: Calculate total distance

$\text{Total distance} = 67 + (6 + 7) = 67 + 13 = 80$

A possible route starting from A is: ABCDABDBCA

Worked example 2: complex network

lightbulbExample

Worked Example: Complex Network

Consider a network with seven vertices (A, B, C, D, E, F, G) and their degrees shown in parentheses: A(5), B(4), C(4), D(5), E(3), F(4), G(3).

The network has a total weight of 176.

Solution:

Step 1: Identify odd nodes

The odd nodes are: A, D, E, G (all have odd degree)

Step 2: List all possible pairings

With four odd nodes, there are three possible pairings:

Pairing 1: AD with EG
Pairing 2: AE with DG
Pairing 3: AG with DE

Step 3: Find shortest routes and totals

Pairing	Shortest route	Length	Total
AD	AC + CD	15	39
EG	EB + BC + CG	24
AE	AB + BE	17	25
DG	DG	8
AG	AG	20	38
DE	DE	18

Step 4: Choose the best pairing

The pairing AE and DG has the smallest total of 25.

Step 5: Repeat arcs AB, BE, and DG

$\text{Total distance} = 176 + 25 = 201$

A possible route starting from A is: ABCDEFABEBFDGCAGDA

Number of possible pairings

The main difficulty with the route inspection algorithm is that the number of possible pairings increases very rapidly as the number of odd nodes increases:

infoNote

Growth of pairings:

Number of odd nodes	Number of pairings
2 odd nodes	1 pairing
4 odd nodes	3 pairings
6 odd nodes	15 pairings
8 odd nodes	105 pairings

For a network with $n$ odd nodes, the number of possible pairings is:

$(n-1) \times (n-3) \times (n-5) \times ... \times 3 \times 1$

chatImportant

Exam tip: You will not be expected to deal with more than 4 odd nodes unless there is extra information given to reduce the number of pairs you need to examine.

How many times does the route pass through a node?

The inspection route may pass through a particular node several times. Each time it uses one arc into the node and one arc out of the node.

infoNote

Key formula: The inspection route passes through a node of degree $n$ exactly $\dfrac{1}{2}n$ times.

For example:

A node of degree 6 is passed through 3 times
A node of degree 4 is passed through 2 times
A node of degree 2 is passed through 1 time

This is useful for answering questions about how many times the route visits specific locations.

Semi-Eulerian networks

Some problems may require different start and finish points. In this case, the network must be made semi-Eulerian.

A semi-Eulerian network has exactly two nodes of odd degree. The route must start at one odd node and finish at the other odd node.

Solving problems with different start and finish points

When you can start and finish at different points:

Identify all odd nodes as usual
Find shortest routes between pairs
Choose the pairing with smallest total
After adding the extra arcs, there will still be exactly two odd nodes remaining
The route must start at one of these odd nodes and finish at the other

infoNote

The total distance is still calculated as:

$\text{Total distance} = (\text{sum of original weights}) + (\text{sum of extra arc weights})$

But now the extra distance is typically smaller because you don't need to return to the starting point.

Worked example 3: cleaning vehicle problem

lightbulbExample

Worked Example: Cleaning Vehicle Problem

A cleaning vehicle must sweep all paths in a park and return to point A. The network shows times in minutes, with a total time of 80 minutes.

Part a: Find the minimum time needed to complete the task.

Solution:

Step 1: The odd nodes are B, C, D, and E

Step 2: List pairings: BC with DE, BD with CE, BE with CD

Step 3: Find shortest routes

Pairing	Shortest route	Length	Total
BC	BE + EC	15	26
DE	DE	11
BD	BA + AD	14	19
CE	CE	5
BE	BE	10	21
CD	CD	11

Step 4: Best pairing is BD and CE with total 19

Step 5: Repeat arcs BA, AD, and CE

$\text{Time needed} = 80 + 19 = 99 \text{ minutes}$

Part b: How many times will the vehicle pass through D?

D has degree 4, so the route passes through D exactly $\dfrac{4}{2} = 2$ times.

Part c: The vehicle can now start and finish at different points. Find the minimum time.

Solution:

With different start and finish points allowed, we need to repeat only one pair of odd nodes.

The route must repeat one pair. The shortest pair is CE = 5, so repeat CE.

$\text{Time needed} = 80 + 5 = 85 \text{ minutes}$

After adding CE, nodes B and D are still odd nodes. The network is semi-Eulerian.

The route must start at B and finish at D (or vice versa).

Strategy for solving route inspection problems

When answering exam questions:

1. Identify nodes with odd degree.

Calculate the degree of each node by counting the arcs at that node.

2. Find the shortest routes between all pairs of odd nodes.

Use inspection or draw directly on the diagram. For each pairing, write down the route and its length.

3. Find which arcs must be added to solve the problem.

Choose the pairing with the smallest total. List the arcs that lie on the shortest routes for this pairing.

4. Answer the question in context.

Calculate the total distance. If asked, write out a possible route or answer other specific questions about the problem (e.g., number of times through a node, start/finish points).

Common exam pitfalls

chatImportant

Watch out for these common mistakes:

Forgetting to add the extra arcs to the original total. Always calculate: original + extra.
Not checking all pairings. With 4 odd nodes, there are 3 possible pairings - you must check all three.
Miscounting degrees. Carefully count how many arcs connect to each node. If an arc is a loop, it contributes 2 to the degree.
Confusing route passes with node degree. A node of degree 6 is passed through 3 times (not 6 times).
For semi-Eulerian problems, forgetting which nodes are odd after adding extra arcs. The route must start and finish at the two remaining odd nodes.
Not showing clear working. In exam questions, always show your pairing table, calculations, and state which arcs are repeated.

Summary

bookmarkSummary

Key Points to Remember:

The route inspection problem seeks the shortest route that travels along every arc at least once and returns to the starting point.
Eulerian networks (all nodes even) can be traversed without repeating any arcs. The total distance is simply the sum of all arc weights.
The algorithm: Identify odd nodes → List pairings → Find shortest routes → Choose minimum total → Repeat those arcs.
Total route length = original arc weights + extra arc weights from the best pairing.
A node of degree $n$ is passed through exactly $\dfrac{1}{2}n$ times during the inspection route.
Semi-Eulerian networks (exactly two odd nodes) are for problems with different start and finish points. The route must begin at one odd node and end at the other.
Every network has an even number of odd-degree nodes.
With 4 odd nodes, you must check all 3 possible pairings to find the minimum.

The Route Inspection Problem (AQA A-Level Further Maths): Revision Notes