The domino inequalities: facets for the symmetric travelling salesman polytope

Adam Letchford has defined the Domino Parity inequalities for the Symmetric Traveling Salesman Polytope (STSP) and has given a polynomial algorithm for the separation of such constraints when the support graph is planar, generalizing a result of Fleischer and Tardos for maximally violated comb inequalities. Naddef has also given a set of necessary conditions for such inequalities to be facet defining for the STSP. These conditions lead to the Domino inequalities and it is shown by Naddef that one does not lose any facet inducing inequality restricting the Domino Parity inequalities to Domino inequalities, except maybe for some very particular case. We prove here that all the domino inequalities are facet inducing for the STSP, settling a conjecture in Naddef's paper. As a by product we will also have a complete proof that the comb inequalities are facet inducing.