A BOUND OF 4 FOR THE DIAMETER OF THE SYMMETRICAL TRAVELING SALESMAN POLYTOPE

We investigate the diameter of the polytope arising in the n-city symm etric traveling salesman problem (TSP) and perfect matching polytopes. Grotschel and Padberg [The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley-Intersci. Ser. Discrete Math., E. Lawler et al., eds., John Wiley, Chichester, 1985, pp. 251-305] conje ctured that the diameter of the symmetric TSP polytope is 2, independe nt of n. We constructively show that its diameter is at most 4, for al l n greater than or equal to 3. Our result also shows that the diamete r of the perfect 2-matching polytope is at most 6, for every n greater than or equal to 3.