The Third Proof of Lovász's Cathedral Theorem
arXiv:1301.7597
Abstract
A graph with a perfect matching is called saturated if has more perfect matchings than for any edge that is not in . 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.
22 pages, 6 figures