In most natural applications of the traveling salesman problem, direct routes are inherently shorter than indirect routes. For example, if the edge weights of the graph are ``as the crow flies'', straight-line distances between pairs of cities, the shortest path from x to y will always be to fly directly.
Figure: The triangle inequality typically holds in geometric
and weighted graph problems.
The edge weights induced by Euclidean geometry satisfy the triangle
inequality, which insists that 
for all triples
of vertices u, v, and w.
The reasonableness of this condition is shown in
Figure 
.
Note that the cost of airfares is an example of a distance function
that violates the triangle inequality, since it is sometimes cheaper to
fly through an intermediate city than to fly to the destination directly.
TSP remains hard when the distances are Euclidean distances in the plane.
Whenever a graph obeys the triangle inequality, we can approximate the optimal traveling salesman tour using minimum spanning trees. First, observe that the weight of a minimum spanning tree is a lower bound on the cost of the optimal tour. Why? Deleting any edge from a tour leaves a path, the total weight of which must be no greater than that of the original tour. This path has no cycles, and hence is a tree, which means its weight is at least that of the minimum spanning tree. Thus the minimum spanning tree cost gives a lower bound on the optimal tour.
Consider now what happens in performing a depth-first traversal of a
spanning tree.
Suppose we walk through each tree edge as we process it in a depth-first
search.
We will visit each edge twice, once going down the tree when exploring it
and once going up
after exploring the entire subtree.
For example, in the depth-first search of Figure ,
we visit the vertices in
order 1-2-1-3-5-8-5-9-5-3-6-3-1-4-7-10-7-11-7-4-1,
thus using every tree edge exactly twice.
Therefore, this tour has weight twice that of the minimum spanning tree, and
hence at most twice optimal.
Figure: A depth-first traversal of a spanning tree, with the shortcut tour
However, vertices will be repeated on this depth-first search tour.
To remove the extra vertices,
at each step we can take a shortest path to the next unvisited vertex.
The shortcut tour for the tree above is
1-2-3-5-8-9-6-4-7-10-11-1.
Because we have replaced a chain of edges by a single direct edge,
the triangle inequality ensures that the tour can only get shorter.
Thus the shortcut tour is within weight twice that of optimal.
More complicated but better approximation algorithms for Euclidean
TSP are mentioned in Section .
No approximation algorithms exist for TSPs that do not satisfy the
triangle inequality.