All subjects · Mathematics · WDM11 (D1)

Route inspection: two odd vertices

The route inspection (Chinese postman) problem asks for the shortest route that travels along every edge at least once and returns to the start. Think of a road gritter or a postman covering every street.

If every vertex is even

The network is Eulerian, so a route using each edge exactly once exists. The shortest route is just the total weight of the network.

Two odd vertices

Some edges must be repeated. The extra distance is the shortest path between the two odd vertices; that path is walked twice. Shortest route = total weight + shortest path between the odd vertices. The shortest path may not be the direct edge: check routes through other vertices.

Writing a route

Add the repeated edges to the network; now every vertex is even, so an Eulerian route exists. Write one out, starting and ending at the given vertex. A vertex of degree d (after adding repeats) is passed through d/2 times.

Start and finish different

If the route may start and finish at different vertices, start at one odd vertex and finish at the other: then no edge needs repeating and the length is just the total weight.

Worked example

Find the length of the shortest inspection route of network R that starts and ends at P.

  1. Total weight = 53
  2. Degrees: P 2, Q 3, R 4, S 3, T 2. Odd vertices: Q, S
  3. Shortest Q to S: direct 13, via R 12, so 12 by QRS
  4. Length = 53 + 12 = 65

Answer: 65, repeating Q-R-S

Key idea: Total weight + shortest path between the two odd vertices; the repeated path may go through other vertices.

Check yourself

  1. Find the length of the shortest route that covers every edge of network R and returns to its start.
    Show answer

    65. Total 53 plus the repeat of QRS (12) gives 65.

  2. In network R, which edges are repeated in the shortest inspection route?
    • QS
    • QR and RS
    • PQ and PR
    • ST and RT
    Show answer

    QR and RS. The odd vertices are Q and S. Q to S directly is 13, but Q to R to S is 12, so QR and RS are repeated.

  3. In network R, how many vertices have odd degree?
    Show answer

    2. Odd: Q, S.

  4. In network R, the route may start and finish at different vertices. What is the length of the shortest route covering every edge?
    Show answer

    53. Start at Q and finish at S (the odd vertices): no edge needs repeating, so the length is the total weight.

  5. After adding the repeated edges, vertex R has degree 6. How many times does the inspection route pass through R?
    Show answer

    3. Each pass uses one edge in and one edge out: 6/2 = 3.

  6. A network has every vertex of even degree and a total weight of 147. What is the length of the shortest route that covers every edge and returns to the start?
    Show answer

    147. All vertices are even, so the network is Eulerian; no edges need repeating.

  7. Why must some edges be repeated when a network has odd vertices?
    • Odd vertices are further away
    • The network is not connected
    • A closed route uses an even number of edge ends at every vertex
    • The algorithm is a heuristic
    Show answer

    A closed route uses an even number of edge ends at every vertex. Every time the route goes into a vertex it must come out again, so each vertex needs even degree.

Practise with instant feedback

Sources

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