Every edge, return to start — The closed route-inspection problem seeks a shortest walk using every edge of a connected undirected network at least once and returning to its starting vertex. Repeated edges are allowed. This differs from a travelling-salesman tour, whose essential requirement is to visit every vertex rather than traverse every original edge.
The unavoidable original total — Let W be the sum of all original edge weights, each counted once. Any route-inspection walk has length at least W. If every vertex is even, an Eulerian circuit uses each edge once and reaches W, proving it minimum. Weights are nonnegative in the route model here.
Why odd vertices need pairing — A closed route has even total traversed degree at every vertex. Repeating a path switches each endpoint degree from odd to even or even to odd but changes intermediate degrees by two. Therefore pair the original odd vertices and duplicate routes joining each pair. The added cost is the sum of the duplicated path lengths, not merely an arbitrary set of direct connecting edges.
Use shortest path distances — For each candidate pair of odd vertices, find the shortest route between them, possibly through even or other vertices. A heavy direct edge may be worse than an indirect path. A Floyd distance matrix can supply these pair costs, but reconstruct the actual original edges to be traversed again.
Exactly two odd vertices — With two odd vertices A and C, duplicate a shortest A-to-C path. For the cycle edges AB3, BC4, CD5, DA6 plus diagonal AC2, the original total is 20 and only A,C are odd. The extra shortest path AC has length 2, so the minimum closed walk is 22.
An actual closed walk — For that network, A–B–C–A–D–C–A traverses AB, BC, CA, AD, DC and CA. Only AC is repeated; its total is 3 + 4 + 2 + 6 + 5 + 2 = 22. A route list verifies that the theoretical added weight is realised rather than merely asserted.
Four odd vertices — For odd vertices A,B,C,D there are three pairings: AB with CD, AC with BD, and AD with BC. Evaluate all three sums using shortest pair distances and choose the least. Greedily selecting the single shortest pair may leave an expensive remaining pair and is not a general minimum-pairing method.
A four-odd example — Use the six edges AB3, AC2, AD6, BC4, BD7, CD5. All four vertices have degree 3 and W = 27. The listed weights are also the shortest pair distances. Pairing totals are AB+CD = 8, AC+BD = 9 and AD+BC = 10. Duplicate AB and CD to obtain minimum closed length 35.
Realising the four-odd result — One minimum walk is A–B–C–D–A–C–D–B–A. It duplicates AB and CD, uses every other edge once, and returns to A. Verify parity in the augmented multigraph and add actual edge traversals; don't count duplicated paths as new physical roads.Blue double lines show the extra traversals of AB3 and CD5, not additional physical roads. Every original vertex has degree 3; duplicating the chosen pairing makes each degree 4. The complete 35-weight closed walk is listed in the associated explanation.
More than four odd vertices — The general method is a minimum-weight perfect pairing of all odd vertices in the shortest-distance network. The specification ordinarily uses at most four odd vertices unless extra information restricts the larger case. Do not test only three pairings if more unmatched odd vertices remain.
Endpoints and interpretation
Open endpoints change parity — If a problem explicitly requires distinct start S and finish T, the augmented graph must have exactly those two odd vertices. Switch the odd/even status of S and T in the original odd-vertex set (remove either if already present, otherwise add it); pair the resulting set and duplicate the cheapest connecting paths. This is an extension of the closed-return method, not a reason to forget the required endpoints.
An open example — For the four-odd network above, requiring start A and finish B leaves C and D to be corrected. Duplicate CD5, giving length 27 + 5 = 32. A valid walk is A–B–D–C–A–D–C–B. The closed optimum 35 does not answer this different endpoint requirement.
Free choice of endpoints — With exactly two original odd vertices and a freely chosen open trail, use those as endpoints and repeat nothing. If a start or finish is fixed differently, recompute the parity requirement. 'At least once' does not mean 'exactly once' when the endpoint constraints prevent an Eulerian trail.
Scope and practical meaning — Route inspection can model gritting roads or checking every connection, but traffic directions, service-side constraints or time windows may require a different problem. A repeated shortest path may pass a vertex several times, which is allowed. Give repeated edges, the minimum length, endpoint conditions and an actual walk when requested.
Travelling-salesman models
Visit vertices and return — A travelling-salesman tour starts at a vertex, visits all required vertices and returns to the start. In the classical problem each other vertex is visited once, forming a Hamiltonian cycle. In the practical problem repeated vertices may be allowed as part of travel on the actual road network.
Complete distance networks — For practical travel, replace each pair by its shortest permitted distance in the original network, using an all-pairs method where needed. This creates a complete distance network for a connected undirected graph. A single distance-network edge may expand into several original roads and pass through other required places.
Triangle inequality — Distances satisfy d(A,C) ≤ d(A,B) + d(B,C) when a direct shortest-distance connection cannot exceed travel via B. The classical metric problem in this course uses complete graphs with this property. Arbitrary supplied costs may not be metric; check the assumption before using shortcut arguments.
Feasible tours give upper bounds — The weight U of any valid tour bounds the optimum from above: optimum ≤ U. A shorter valid tour improves this upper bound. Merely adding the smallest n edges can produce disconnected cycles or unsuitable degrees and is not a valid tour certificate.
Nearest neighbour method — From the specified start, repeatedly choose the nearest unvisited vertex, resolving ties as stated; once all are visited, return to the start. This heuristic produces a tour but need not be optimal. Trying several starting vertices may improve the bound, while a question prescribing one start still requires that specific trace.
A worked nearest-neighbour tour — Use complete distances AB4, AC6, AD5, BC3, BD7, CD4. Starting at A, choose B4, then C3, then D4 and return via DA5, giving A–B–C–D–A of total 16. Compare only currently unvisited vertices at each choice, not already visited nearer ones.
An independent optimum check for four vertices — Up to reversal and starting-point rotation, the distinct A-start tours are A–B–C–D–A = 16, A–B–D–C–A = 21, and A–C–B–D–A = 21. Here enumeration proves 16 optimal. The nearest-neighbour method alone would not supply that general proof.
Tree-based lower and upper bounds
Spanning-tree lower bound — Removing one edge from any tour leaves a spanning tree, so a minimum spanning tree weight is no larger than that tour. This gives a lower bound, although it is often weak because a tour must return and every tour vertex has degree two.
Delete-a-vertex lower bound — Choose vertex V, delete it and all its edges, find a minimum spanning tree on the remaining vertices, then add the two smallest original edges incident to V. Any Hamiltonian tour minus V and its two tour edges leaves a spanning path on the remainder, whose weight is at least that minimum tree. The two incident tour edges cost at least the two smallest available incident weights.
A worked lower bound — Deleting A from the worked complete graph leaves BC3, CD4 and BD7, whose minimum tree uses BC and CD with total 7. The two cheapest edges incident to A are AB4 and AD5, total 9. The lower bound is 7 + 9 = 16, matching the nearest-neighbour upper bound and proving the 16 tour optimal.The lower argument uses the remaining minimum tree plus the two cheapest incident connections. The upper argument exhibits an actual tour. Their agreement proves this example optimal; the nearest-neighbour heuristic alone would not prove the general claim.
Several lower bounds — Repeat the delete-a-vertex procedure at other vertices if requested. Since every result is a valid lower bound, the largest is the strongest one. By contrast, among valid tour upper bounds choose the smallest. Do not swap these directions when comparing numerical results.
Double-tree upper bound — Duplicate every edge of a minimum spanning tree to make all degrees even. An Eulerian walk then visits every vertex and returns with weight 2M, where M is the tree weight. This is a valid practical tour and an upper bound. In a complete metric graph, shortcut repeated vertices to produce a classical tour of no greater length.
Why shortcutting is safe in the metric case — If a walk goes A–B–C and B has already been visited, replace that part with A–C. The triangle inequality ensures d(A,C) ≤ d(A,B) + d(B,C), so length does not increase. Keep one visit to each required vertex and close the tour; removing a required vertex's only visit would make the result invalid.
A doubled-tree example — For the worked graph, a minimum spanning tree (MST) is BC3, AB4 and CD4, with M = 11. Doubling gives an Eulerian walk of length 22, such as A–B–C–D–C–B–A. Shortcut repeated C and B after D using direct DA5, producing A–B–C–D–A of length 16. The improvement uses the metric complete distances.
Bounds do not normally coincide — If a lower bound L is below a feasible tour U, all that is established is L ≤ optimum ≤ U. The lower bound need not be attainable and the heuristic upper bound need not be optimal. The numerical gap describes remaining uncertainty; do not assert a specific optimum without additional evidence.
Expand a practical route — Translate each chosen shortest-distance connection back into its original network path before giving road instructions or checking feasibility. Repeated vertices introduced by this expansion are permitted in the practical problem. Keep the classical Hamiltonian tour in the complete distance model distinct from its expanded physical walk.
A complete optimisation argument — State whether the requirement is every edge or every vertex, whether endpoints match, which distances and restrictions apply, how the proposed solution was constructed and whether optimality is proved or only bounded. Include complete routes and calculations so a teacher can assess the extended reasoning that short quizzes sample only partially.
Test yourself
50 questions · Random sets of 10. These quick checks support revision; practise longer explanations and justified judgements too.
Mr Kidman's Classroom
