THE SKELETON OF THE SYMMETRICAL TRAVELING SALESMAN POLYTOPE

The vertices of the skeleton of the symmetric Traveling Salesman Polytope are the characteristic vectors coffesponding to the Hamiltonian tours in the complete graph K(n) with n greater-than-or-equal-to 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 K(n) 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 1/2(n-2)! cliques, and has diameter at most n-3