1-tree

For a designated root vertex in an undirected complete graph, a 1-tree consists of a spanning tree on all other vertices together with two distinct root-incident edges. It is connected and has exactly one cycle, which passes through the root. Its minimum weight is the cost of an independent minimum spanning tree plus the two cheapest root edges, computable in quadratic time on a dense graph by Prim's algorithm.

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.