Metric TSP And Triangle-Inequality Shortcutting

Metric Costs and Repeated Visits

A route that visits every city need not visit each city exactly once. It may return to a city already visited, then continue to a city it has not yet reached. For metric Traveling Salesman Problems, repeated visits can be removed without increasing the route cost. The essential condition is the triangle inequality: travelling directly between two vertices costs no more than travelling between them through an intermediate vertex.

Throughout, let \(n\ge 3\). The underlying graph is the complete undirected simple graph \(G=(V,E)\), where \(|V|=n\) and \(E\) contains every unordered pair of distinct vertices. Thus there is an edge between every pair of different vertices. An edge cost is a function \(c\) assigning a real number to each such edge.

A closed walk visiting all vertices is a sequence \(w_0,w_1,\ldots,w_\ell\) with \(w_\ell=w_0\), consecutive vertices adjacent, and every vertex of \(V\) appearing in the sequence. It may repeat vertices and edges. In contrast, a Hamiltonian tour has the form \(v_0,v_1,\ldots,v_{n-1},v_0\), where \(v_0,\ldots,v_{n-1}\) are distinct and include every vertex. Its cost is \(\sum_{i=0}^{n-1}c(v_i,v_{i+1})\), with \(v_n=v_0\). The final return to \(v_0\) is part of the tour; a longer closed walk with further visits is not a Hamiltonian tour.

Cost Along a Walk

The triangle inequality applies not only to one intermediate vertex, but to an entire walk. This fact is what permits a whole section of a route to be replaced by one edge.

Proof. We use induction on the number \(k\ge1\) of edges in the walk. If \(k=1\), the two sides are equal. Suppose \(k\ge2\) and the assertion holds for walks with \(k-1\) edges. The triangle inequality, applied with intermediate vertex \(x_{k-1}\), gives \(c(x_0,x_k)\le c(x_0,x_{k-1})+c(x_{k-1},x_k)\). By the induction hypothesis, \(c(x_0,x_{k-1})\le\sum_{j=0}^{k-2}c(x_j,x_{j+1})\). Adding \(c(x_{k-1},x_k)\) proves the claimed bound. The argument allows repeated vertices: the metric definition includes \(c(u,u)=0\), so such repetitions cause no exception. \(\square\)

Shortcutting to a Hamiltonian Tour

Proof. Let \(w_0,w_1,\ldots,w_\ell\) be a closed walk visiting all vertices, with \(w_\ell=w_0\). For each vertex, record its first appearance among \(w_0,\ldots,w_{\ell-1}\). List these first appearances in order as \(w_{i_0},w_{i_1},\ldots,w_{i_{n-1}}\), where \(i_0=0<i_1<\cdots<i_{n-1}<\ell\). This list contains every vertex exactly once. Form the tour that follows this order and then returns from \(w_{i_{n-1}}\) to \(w_0\).

For each \(r\) with \(0\le r<n-1\), the part of the original walk from \(w_{i_r}\) to \(w_{i_{r+1}}\) has cost \(\sum_{j=i_r}^{i_{r+1}-1}c(w_j,w_{j+1})\). By the Lemma, this is at least \(c(w_{i_r},w_{i_{r+1}})\), the cost of the tour edge that replaces it. The final part of the walk runs from \(w_{i_{n-1}}\) to \(w_\ell=w_0\); the Lemma shows that its cost is at least \(c(w_{i_{n-1}},w_0)\). These parts partition all edges of the original walk. Adding their inequalities shows that the constructed Hamiltonian tour costs no more than the walk. Its listed vertices are distinct and include all of \(V\), and its last edge returns to its starting vertex, so it is a Hamiltonian tour as defined. \(\square\)

The construction keeps the first occurrence of each vertex and replaces each intervening section of the walk by a direct edge. Completeness guarantees that each replacement edge exists; the metric condition guarantees that its cost does not exceed the cost of the section it replaces.

Why the Metric Condition Matters

The theorem depends on the triangle inequality, not merely on having costs assigned to every edge. Without that condition, an edge that skips part of a walk can be more expensive than the section it replaces. The next example shows that even positive, symmetric costs on a complete graph are not enough.

What Shortcutting Does—and Does Not—Say

One consequence is that, in a metric TSP instance, allowing a closed route to repeat vertices does not produce a lower minimum cost than requiring a Hamiltonian tour. Every Hamiltonian tour is itself a closed walk visiting all vertices. In the other direction, the theorem converts any such closed walk into a tour of no greater cost. Thus the least cost among Hamiltonian tours is no greater than the cost of any covering closed walk, while tours are already among the covering closed walks. These two comparisons give equality of the minimum costs.

This conclusion concerns the complete graph with metric costs. If a graph is not complete, a shortcut edge may not exist. If the costs are not metric, that edge may exist but be too expensive. Nor does shortcutting say that every repeated visit can be removed while keeping an arbitrary prescribed order of all other visits. The construction instead takes the vertices in their order of first appearance and uses the metric inequality to bound the resulting tour cost.

Common mistake. It is incorrect to argue that a repeated-vertex walk can always be shortened because “the direct edge is shorter.” In the nonmetric example, the direct edge \(bc\) costs \(10\), while the route \(b,a,c\) costs \(1+1=2\). The valid correction is to invoke the triangle inequality for each replaced section; without it, no nonincrease is guaranteed. It is also important to check the endpoint of the tour: after listing the \(n\) distinct vertices, the sequence must return immediately to its starting vertex, with no extra visits.