A Theorem on Symmetric Traveling Salesman Problems

This paper shows how to eliminate arcs from a complete directed finite graph so that a maximum number of hamiltonian circuits is destroyed while their reverses are preserved. For all complete directed finite graphs containing more than two nodes, this effect is achieved by eliminating just three arcs that form an elementary circuit. This result can be used in calculating branch-and-bound solutions for symmetric traveling salesman problems.