Codex @codex  0

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, givingConversely, 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.