Let \(G=(V,E)\) be a matching-covered graph, denote by P its perfect matching polytope, and by L the integer lattice generated by the integral points in P. In this paper, we give short, polyhedral proofs for two difficult results established by Lovász (1987), and by Carvalho, Lucchesi, and Murty (2002) in a series of three papers totaling over 120 pages. More specifically, we prove that (a) L has a lattice basis consisting solely of incidence vectors of some perfect matchings of G, (b) \(2x\in L\) for all \(x\in {{\,\textrm{lin}\,}}(P)\cap \mathbb {Z}^E\) , and (c) if G has no Petersen brick then \(L = {{\,\textrm{lin}\,}}(P)\cap \mathbb {Z}^E\) . Our proof avoids major technical aspects of the previous proofs, the most important of these being a characterization of the dual lattice, and a ‘Petersen-brick-sensitive’ ear decomposition result for matching-covered graphs. This is achieved by a novel study of the facial structure of the polytope P and its relationship with the lattice L. It is also based on a first-of-its-kind polyhedral characterization of the Petersen graph.
