• The Route Inspection Problem (a.k.a. the Chinese Postman Problem) asks for the shortest route that travels along every edge of a graph and returns to the start.
• Whether you need to repeat any edges depends entirely on the degree (order) of each vertex — specifically, how many vertices have an odd degree.
• 0 odd vertices → the graph is Eulerian → no repeats needed at all.
• 2 odd vertices → the graph is semi-Eulerian → you must repeat the shortest path connecting those two odd vertices.
• More than 2 odd vertices (always an even number of them) → you must test every possible way of pairing them up, and repeat whichever pairing gives the smallest total.
• The final answer = (sum of all edge weights in the original graph) + (sum of the weights of the repeated edges).

Picture a real postman. Every morning he has to walk down every road on his route to deliver letters. He starts at the depot, and he has to end back at the depot. Naturally, he wants to walk the shortest possible total distance while still covering every road at least once.

The catch: road networks are messy. Sometimes the layout of roads means it's mathematically impossible to walk every road exactly once and return to the start — some roads will have to be walked twice. The question the algorithm answers is: which roads should be repeated to keep the extra distance as small as possible?

Formal definition

Given a weighted graph, find the route of least total weight that:

• Traverses every edge in the graph at least once, and
• Starts and finishes at the same vertex.

Common variations you might be asked about

• Different start and finish vertices — e.g. a delivery van starts at the depot but ends its shift at home.
• Edges disregarded — e.g. a particular road is closed for roadworks, so it's removed from the graph entirely.
• Routes that require deliberate repetition — e.g. a road-sweeping lorry that has to sweep both sides of every road, meaning every edge is effectively walked twice on purpose (this doubles every edge weight rather than looking for odd vertices).

Everything in this chapter hinges on one very simple first step: for every vertex in the graph, count how many edges are connected to it. This number is called the degree (or order) of the vertex. Then sort vertices into two piles: even degree and odd degree.

Why does this matter so much? Because of a beautiful piece of graph theory (first worked out by Euler himself, hence "Eulerian"): a route that uses every edge exactly once and returns to its start point (called an Eulerian circuit) is only possible if every single vertex has an even degree. If even one vertex has an odd degree, you literally cannot draw that route without retracing a line — it's a mathematical impossibility, not just something that's hard to find.

Why odd vertices force a repeat

Think about walking through a vertex: every time you arrive along one edge, you must leave along a different edge — arrivals and departures use up edges in pairs. If a vertex has an even degree, every visit pairs up perfectly and you can leave the way you haven't been before, right up until the last edge, which brings you home. But if a vertex has an odd degree, at some point you'll arrive and find every other edge already used — except the one that brought you there. You get "stuck" needing to reuse an edge. That's the mathematical root of why odd vertices cause the problem.

Case A — 0 odd vertices (the graph is Eulerian)

This is the easy, best-case scenario. If every vertex has even degree, an Eulerian circuit exists — a route that travels along every edge exactly once and returns to the start. No edges need to be repeated at all.

Case B — 2 odd vertices (the graph is semi-Eulerian)

This is where the real "route inspection" thinking kicks in. If exactly two vertices have odd degree, the graph is called semi-Eulerian. This means there's a route that travels every edge exactly once, but it can only do so if it starts at one odd vertex and finishes at the other — not a closed loop.

Two situations can arise here, and it's crucial you spot which one a question is actually asking:

• If the route must start and finish at the SAME vertex (the standard Chinese Postman setup): you cannot avoid repeating something, because a closed route needs every vertex to be even. You must find the shortest path between the two odd vertices and repeat every edge along that path.
• If the route is allowed to start at one odd vertex and finish at the other: no repetition is needed at all! The Eulerian path already exists between those two points.

Worked Example — Cable Network (2 Odd Vertices)

A network shows the distance, in metres, of cables between connection points A, B, C, D, E and F. Every cable must be inspected, and the engineer must start and finish at connection point E.

Step 1 — Inspect the degree of every vertex

Step 2 — Find the shortest path between the odd vertices

There's exactly one pair of odd vertices: A and C. The direct edge AC = 16, but going via B (A→B→C = 9 + 5 = 14) is shorter. So the shortest path between A and C is A–B–C, weight 14, meaning edges AB and BC must be repeated.

Step 3 — Write down an Eulerian circuit of the adjusted graph

One possible route: E F A E D A B A C B C E

Step 4 — Calculate the total

Real road networks are messy, and it's very common for a graph to have 4 (or more) odd vertices. Remember: it will always be an even number (2, 4, 6...) — never odd — because of the rule from Section 2. When there are more than 2 odd vertices, you can't just pick the obvious pairing — you have to be systematic.

The core idea

With 4 odd vertices — call them P, Q, R and S — you need to pair them up into two pairs, and there are exactly 3 different ways to do this:

• PQ and RS
• PR and QS
• PS and QR

For each of these 3 pairings, you find the shortest path for each pair and add the two path lengths together. Whichever pairing gives the smallest combined total tells you which edges to repeat.

What if there are 6 odd vertices?

In theory you'd need to check 15 different pairings — which is a lot of work by hand! In practice, exam questions with more than 4 odd vertices almost always give you extra information (like specifying different start and end points) that effectively reduces the problem back down to 4 odd vertices, so you rarely need to actually do all 15.

Worked Example — Pothole Inspection (4 Odd Vertices)

The network below shows distances, in km, of main roads between towns A, B, C, D and E. Every road must be inspected for potholes, starting and finishing at town A.

(AE curved top edge = 17 km — labelled above the arc)

Step 1 — Inspect the degree of each vertex

There are 4 odd vertices: A, B, C, D. So the network does not contain an Eulerian circuit.

Step 2 — List all 3 possible pairings

The smallest combined total comes from pairing AD and BC, so these edges get repeated.

Step 3 — Eulerian circuit of the adjusted graph

One valid route starting and ending at A: A D A B D C B C E A

Step 4 — Calculate the total

Variation A — Choosing your own start and finish points

Sometimes with 4 odd vertices, a question says the route can start and finish at any two of the odd vertices — you get to choose which two, in order to minimise distance. The method changes slightly:

Variation B — Different weight for first pass vs. repeat pass

In some real-world contexts (e.g. inspecting a pipeline for defects), travelling an edge for the first time might take longer than travelling it again just to "pass through" it (perhaps because the first pass involves careful inspection, while the second pass is just transit). If a question gives you two different weights for an edge — one for "first traversal" and one for "repeat traversal" — make sure you use the correct one at the correct stage of your working. Don't just double the same number if the question specifies otherwise!

Variation C — Roads that must be doubled deliberately

A road-sweeper or line-painter often has to cover both sides of every road. In this case, every edge is effectively duplicated from the start — you're not looking for odd vertices at all, because after duplicating every edge, every vertex's degree automatically doubles and becomes even. The route length is simply 2 × (sum of all edge weights).

Key Terms

Formulas at a Glance

The 4-Step Method (memorise this order!)

• I can explain what the Route Inspection / Chinese Postman Problem is asking for.
• I can find the degree (order) of every vertex in a graph.
• I understand why an Eulerian circuit needs 0 odd vertices.
• I know that the number of odd vertices in any graph is always even.
• I can solve a route inspection problem with 0 odd vertices (Eulerian).
• I can solve a route inspection problem with 2 odd vertices (semi-Eulerian), same start/finish.
• I know the difference in method when start/finish are allowed to be the two odd vertices themselves.
• I can list all 3 possible pairings for a graph with 4 odd vertices.
• I can calculate the shortest path for each pairing and choose the cheapest to repeat.
• I can write down a valid Eulerian circuit for the adjusted graph.
• I can calculate the final total weight (original edges + repeated edges).
• I understand the "choose your own start/finish" variation and why it reduces repeats.
• I understand how deliberate doubling (e.g. road sweepers) differs from the standard problem.