The perfect matching polytope and solid bricks

摘要

The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of perfect matchings of G. Edmonds (J. Res. Nat. Bur. Standards Sect. B 69B 1965 125) showed that a vector x in Q(E) belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) x greater than or equal to 0 (non-negativity), (ii) x (partial derivative(v)) = 1, for all v is an element of V (degree constraints) and (iii) x(partial derivative(S)) greater than or equal to 1, for all odd subsets S of V (odd set constraints). In this paper, we characterize graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. We also present a proof of a recent theorem of Reed and Wakabayashi. (C) 2004 Elsevier Inc. All rights reserved.