The Third Proof of Lovász's Cathedral Theorem

Original · EN

A graph G with a perfect matching is called saturated if G+e has more perfect matchings than G for any edge e that is not in G. Lovász gave a characterization of the saturated graphs called the cathedral theorem, with some applications to the enumeration problem of perfect matchings, and later Szigeti gave another proof. In this paper, we give a new proof with our preceding works which revealed canonical structures of general graphs with perfect matchings. Here, the cathedral theorem is derived in quite a natural way, providing more refined or generalized properties. Moreover, the new proof shows that it can be proved without using the Gallai-Edmonds structure theorem.