Seminar - Nishad Kothari

Ear-decompositions of nonbipartite matching-covered graphs

Abstract: 

A connected graph is called matching-covered if each edge lies in a perfect matching. A classical result of Lovasz (1983) states that every nonbipartite matching covered graph either "contains" $K_4$, or "contains" the triangular prism (complement of a 6-cycle). Carvalho and Lucchesi (1996) gave a much simpler proof of this fundamental and very useful result. I will present their proof. I will also present an application due to Lovasz, which gives a different characterization of graphs with the Konig property (size of max. matching = size of min. vertex cover).