One disadvantage of the minimum spanning tree relaxation is that it is
a very weak relaxation: it tends to be far from the optimal solution.
One reason for this is that it does not even include the right number
of edges in the solution (it has |*V*|-1 while the optimal tour has
|*V*|). This can be corrected by finding the optimal *one-tree*.

A one-tree is a tree together with one extra edge. This extra edge forms a single cycle. If this cycle goes through all the nodes, then the result is a tour, but it is not necessary for all nodes to be on the cycle.

Suppose we choose a node *A*, and find the cheapest one-tree where
the single cycle includes node *A* and for which *A* is incident to
exactly two nodes. This is clearly a relaxation, for
the optimal tour is a one-tree whose cycle includes *A* but the
optimal tour may not be the cheapest such one-tree.

Here is an algorithm to find such a one-tree. Let *G*=(*V*,*E*) be the
original graph. Let *G*' be the graph that takes *G* and deletes *A*
and all edges incident to *A*. Let *T*' be the minimum spanning tree
in *G*. Create *T* by adding the two cheapest edges incident to *A*
in *G*. *T* is a one-tree and turns out to be the cheapest one-tree
whose cycle includes node *A* and two edges incident to *A*.
Figure 2 illustrates this for our example.

Of course, the choice of *A* is arbitrary. If we want to find the
``best'' one-tree, we can repeat this for for all nodes and choose
the most expensive. This will give the best relaxation bound. In our
example, the best relaxation occurs when we use node *E*. This gives
the one-tree in figure 3.

We now know that the optimal tour in our example is either 14, 15, or 16.

Mon Nov 11 15:16:52 EST 1996