Route inspection and odd vertices

What you’ll learn

• Identify odd-degree vertices.
• Compare shortest-path pairings of odd vertices.
• Construct a minimum closed route covering every edge.

Understand the idea

Route inspection asks for the shortest closed walk that traverses every edge of a connected undirected network at least once. If all vertex degrees are even, an Eulerian circuit uses every edge exactly once. Its length is simply the sum of all edge weights.

If odd vertices are present, duplicate paths so all degrees become even. With two odd vertices, duplicate their shortest connecting path. With four odd vertices, compare all three pairings using shortest-path distances, not automatically the direct edge weights. Choose the cheapest total duplication.

Add the duplicated distance to the sum of the original edge weights. A route must then be traced on the resulting multigraph, using each original and duplicated edge the required number of times. This solves the closed version; allowing distinct start and finish vertices changes the parity requirement.

Key formulae

$$\sum_{v\in V}\deg(v)=2|E|$$

$$L_{\min}=\sum_{e\in E}w(e)+\min(\text{odd-vertex pairing cost})$$

$$\min\{d(A,B)+d(C,D),\ d(A,C)+d(B,D),\ d(A,D)+d(B,C)\}$$

Worked example

An undirected network has exactly edges AB = 3, BC = 4, CD = 5, DA = 6 and AC = 2. Find a shortest closed route covering every edge at least once.

1. A and C have degree 3; B and D have degree 2. The only odd vertices are A and C.
2. The shortest path between A and C is their direct edge of length 2. Duplicate it.
3. The original total is $3+4+5+6+2=20$, so the minimum closed length is $20+2=22$.
4. One valid route is A–B–C–A–D–C–A; it uses AC twice and every other edge once.

Answer: Minimum length 22, for example A–B–C–A–D–C–A.