The skeleton of the symmetric Traveling Salesman Polytope

The vertices of the skeleton of the symmetric Traveling Salesman Polytope are the characteristic vectors corresponding to the Hamiltonian tours in the complete graph with , and the edges of this skeleton are the 1-faces of the polytope. It is shown that this skeleton contains a Hamiltonian tour such that the Hamiltonian cycles in corresponding to two successive vertices differ in a single interchange, i.e., the interchange graph corresponding to the TSP-polytope is Hamiltonian. It is also shown that the skeleton can be covered by cliques, and has diameter at most .