Total 40, shortest pairing 6
route
46.
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.
This page is easier if you are comfortable with:
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.
Route inspection finds the shortest tour that uses every road. Odd vertices force some roads to be repeated.
The repeated diagonal costs 5 extra on top of the 19 for all the edges.
These examples are worked by hand, step by step, so you can compare your own working.
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.
A square network of side 5 has all vertices of degree 2. Find the route length.
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.
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
route
46.
route
29.
extra
0.
AB+CD vs AC+BD vs AD+BC
3 pairings.
If all vertices are even, the route is the sum of edges. Otherwise add the shortest total pairing of odd vertices.
Total 40, pairing 6.
Total 25, pairing 4.
Extra.
Possible pairings.
total only ✗
add the pairing ✓
Repeats needed.
longest ✗
shortest ✓
Minimise.
even ✗
odd vertices ✓
Odd need pairing.
must return ✗
closed route ✓
Chinese postman.
Try each one on paper, then open the answer. Use the solver above to see the full working.
61
38
71
15
21
107
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
The shortest closed route covering every edge.
The route equals the total length.
Add the shortest pairing.
3.
Euler circuits and trails.
travelling salesperson bounds.
More in Discrete maths and number theory and the formula sheets.