On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph (Q1850603)

A matching covered graph is a nontrivial connected graph in which every edge is contained in some perfect matching. A matching covered graph \(G\) is bicritical if, for any two of its vertices \(u\neq v\), the graph \(G-\{u,v\}\) has a perfect matching. Finally, a brick is a 3-connected bicritical graph. In the two parts of the series [here Part I, for Part II see J. Comb. Theory, Ser. B 85, 137-180 (2002; Zbl 1024.05070 below)] it is proved that, if \(G\) is a brick different from \(K_4\), \(\overline{C}_6\) and \(R_8\), that does not have the Petersen graph as its underlying simple graph, then it has two edges \(e\) and \(f\) such that both \(G-e\) and \(G-f\) are matching covered graphs with exactly one brick, with the additional property that, in each case, the underlying simple graph of that one brick is different from the Petersen graph. This answers in the affirmative a conjecture of Lovász, which states that every brick \(G\) different from \(K_4\), \(\overline{C}_6\), and the Petersen graph has an edge \(e\) such that \(G-e\) is a matching covered graph with exactly one brick.