Route Inspection Explained with Worked Examples

The shortest route that travels along every edge of a connected network and returns to the start has length equal to the sum of all edge lengths, plus the shortest total length needed to pair up the odd vertices.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

What Route inspection (Chinese postman) means

A circuit using every edge exactly once exists when all vertices have even degree; see Euler circuits and trails. In that case the route length is just the total of the edges. Otherwise, odd vertices occur in an even number (handshaking lemma); repeat some edges so that every vertex becomes even, choosing the repeats of least total length by pairing the odd vertices along shortest paths.

Example: rectangle A–B–C–D with sides 3, 4, 3, 4 and a diagonal AC of length 5. A and C have degree 3 (odd); the shortest path between them is the diagonal (5, shorter than 3 + 4 = 7). Total edges , plus 5 gives 24. For a square of side 5, all degrees are 2, so the route is 20. For four odd vertices, compare the three possible pairings and take the smallest.

The method is the Chinese postman problem, solved by a short enumeration of pairings. It differs from the travelling salesperson problem, which visits every vertex once. The networks are graphs as in complete graphs and bipartite graphs; the shortest paths are found by comparing sums, as in critical path analysis.

What is it used for?

Route inspection finds the shortest tour that uses every road. Odd vertices force some roads to be repeated.

How to use route inspection (chinese postman)

  1. List the degrees; if all are even, the answer is the sum of the edge lengths.
  2. Otherwise list the odd vertices and all ways to pair them.
  3. Find the shortest path between the vertices of each pair and total each pairing.
  4. Add the smallest pairing total to the sum of the edges.

Graph

Route length 24 = edges 19 + repeated path 5edges: 19repeat: 5route: 2400.511.522.533.540510152025Route length 24 = edges 19 + repeated path 5partyGraph with x from 0 to 4 and y from 0 to 28. Shows bars (3); point edges: 19 at (1, 19); point repeat: 5 at (2, 5); point route: 24 at (3, 24).

The repeated diagonal costs 5 extra on top of the 19 for all the edges.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: two odd vertices

A rectangle has sides AB 3, BC 4, CD 3, DA 4 and a diagonal AC of length 5. Find the shortest route that covers every edge and returns to the start.

Worked example
Answer
2424
  1. Sum of edges
  2. Odd vertices A and C: shortest path
  3. Route

Example 2: all even

A square network of side 5 has all vertices of degree 2. Find the route length.

Worked example
Answer
2020
  1. Sum of edges

Example 3: four odd vertices

Four vertices A, B, C, D are joined in every pair: AB 2, BC 3, CD 2, DA 3, AC 4, BD 4. Find the route length.

Worked example
Answer
2222
  1. Total of edges
  2. Pairings
  3. Smallest

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Total 40, shortest pairing 6

route

46.

Total 25, pairing 4

route

29.

All vertices even

extra

0.

Odd vertices A, B, C, D pairings

AB+CD vs AC+BD vs AD+BC

3 pairings.

Word problems

If all vertices are even, the route is the sum of edges. Otherwise add the shortest total pairing of odd vertices.

Route

Total 40, pairing 6.

  1. 40 + 6
  2. Check: ✓46

Route

Total 25, pairing 4.

  1. 25 + 4
  2. Check: ✓29

No odd vertices Higher

Extra.

  1. 0
  2. Check: ✓0

Four odd vertices Higher

Possible pairings.

  1. 3
  2. Check: ✓3

Common mistakes

Skipping the pairing

total only ✗

add the pairing ✓

Repeats needed.

Longest pairing

longest ✗

shortest ✓

Minimise.

Counting even vertices

even ✗

odd vertices ✓

Odd need pairing.

Ignoring the start

must return ✗

closed route ✓

Chinese postman.

Exam tips

  1. List the odd vertices.
  2. Pair them in all ways.
  3. Choose the shortest.
  4. Route = total + pairing.
  5. Even vertices need nothing.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Route: total 52, pairing 9 Foundation

61

2. Route: total 33, pairing 5 Foundation

38

3. Route: total 71, no odd vertices Foundation

71

4. Pairings for 6 odd vertices Higher

15

5. Route: total 18, pairing 3 Higher

21

6. Route: total 95, pairing 12 Higher

107

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Route inspection
Chinese postman.
Odd vertex
Odd degree.
Pairing
Matching odd vertices.
Eulerian
All even degrees.
Network
Weighted graph.
Repeated edge
Traversed twice.

Frequently asked questions

What is route inspection?

The shortest closed route covering every edge.

What if all vertices are even?

The route equals the total length.

What if some are odd?

Add the shortest pairing.

How many pairings for 4 odd vertices?

3.

Which page covers Euler circuits?

Euler circuits and trails.

Which page covers the travelling salesperson?

travelling salesperson bounds.

More in Discrete maths and number theory and the formula sheets.