In addition to good feasible tours one would like to have some guarantee on the quality of the solutions found. Such a guarantee can be given if a lower bound for the length of the shortest possible tour is known. Then the optimum solution of the relaxed problem gives a valid lower bound for the value of the minimum solution of the original problem.
Different relaxations provide different lower bounds.
The main goal is to find relaxation problems for the TSP that can be solved efficiently and which give lower bounds as tight as possible. The 1-tree bound for the TSP is based on the following observation. Hence we obtain a relaxation of the TSP if we take as feasible solutions arbitrary spanning trees on the node set plus two additional edges incident to node 1. Such a graph contains precisely one circle and is called 1-tree . The lower bounds provided by the 1-tree relaxation are rather poor, as can be seen using the applet below.