Optimal ear decompositions of matching covered graphs and bases for the matching lattice (Q1850602)

A single ear of a graph \(G\) is a path of odd length all of whose internal vertices, if any, have degree equal to two in \(G\). A double ear of \(G\) is a pair of vertex-disjoint single ears of \(G\). An ear decomposition of a matching covered graph \(G\) is a sequence \(G_1\subset G_2\subset \dots \subset G_r\) of matching covered subgraphs of \(G\) where \(G_1=K_2\), \(G_r=G\), and for \(1\leq i\leq r{-}1\), \(G_{i+1}\) is the union of \(G_i\) and an ear (single or double) of \(G_{i+1}\). A Petersen brick is a graph whose underlying simple graph is isomorphic to the Petersen graph. For a matching covered graph \(G\), \(b(G)\) denotes the number of bricks of \(G\), and \(p(G)\) denotes the number of Petersen bricks of \(G\). An ear decomposition of \(G\) is optimal if, among all ear decompositions of \(G\), it uses the least possible number of double ears. Applying the main theorem of their two papers [J. Comb. Theory, Ser. B 85, 94-136 (2002; Zbl 1024.05069) and 137-180 (2002; Zbl 1024.05070)], the authors prove that the number of double ears in an optimal ear decomposition of a matching covered graph \(G\) is \(b(G)+p(G)\). Using this theorem, the authors give an alternative proof of the Lovász matching lattice characterization theorem. As a consequence, there is a base of the matching lattice consisting of matchings associated with the optimal ear decomposition.