Matching covered graphs and subdivisions of \(K_ 4\) and \(\bar C_ 6\) (Q1924125)

A connected graph is matching covered if each of its edges lies in some perfect matching and bicritical if deletion of any two of its vertices yields a graph having a perfect matching. A 3-connected bicritical graph is called a brick. A subgraph \(H\) of a matching covered graph \(G\) is nice if \(G- H\) has a perfect matching. An odd subdivision of a graph \(G\) is a graph obtained from \(G\) by subdividing each edge in an odd number of edges. This paper gives a very simple proof that every non-bipartite matching covered graph contains a nice subgraph that is an odd subdivision of \(K_4\) or \(\overline{C_6}\). It follows immediately that every brick different from \(K_4\) and \(\overline{C_6}\) has an edge whose removal preserves the matching covered graph property. These are classical and very useful results due to Lovász.