= Solution
Delete vertex one and its two incident edges from a <Hamiltonian cycle>. The remaining edges form a Hamiltonian path through all other vertices, hence a <spanning tree>. Thus every tour is a <one-tree>, and both problems use the same edge-cost objective. The relaxation enlarges the feasible set, giving
$$
\boxed{z^{(1)}\leq z^{(2)}.}
$$
Conversely, a <one-tree> in which every vertex has degree two is connected and two-regular, so it is a <Hamiltonian cycle>. Such a minimum <one-tree> therefore also solves the travelling-salesman problem. This is the <one-tree travelling-salesman bound>.
Back to article page
