One-tree travelling-salesman bound
= One-tree travelling-salesman bound
{title2=$z_{1\text{-tree}}\leq z_{\mathrm{TSP}}$}
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.