The skeleton of the symmetric traveling salesman polytope

AbstractThe vertices of the skeleton of the symmetric Traveling Salesman Polytope are the characteristic vectors corresponding to the Hamiltonian tours in the complete graph Kn with n ⩾3, 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 Kn 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 12(n−2)! cliques, and has diameter at most n−3