A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone
In this short communication, we observe that the Graphical Traveling Salesman Polyhedron is the intersection of the positive orthant with the Minkowski sum of the Symmetric Traveling Salesman Polytope and the polar of the metric cone. This follows almost trivially from known facts. There are nonetheless two reasons why we find this observation worth communicating: It is very surprising; it helps us understand the relationship between these two important families of polyhedra.
graphical traveling salesman polyhedron symmetric traveling salesman polytope metric cone hamilton cycle polytope