 One-tree travelling-salesman bound

Deleting a vertex from a Hamiltonian cycle leaves a spanning path, so every travelling-salesman tour is a one-tree. Minimizing the same edge cost over one-trees therefore gives a lower bound for the travelling salesman problem. A connected one-tree with every degree two is itself a Hamiltonian cycle, and a minimizing such one-tree certifies the tour optimum.