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.
