×

An alternative proof of Lovász’s cathedral theorem. (English) Zbl 1301.05264

Summary: 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\). L. Lovász [Acta Math. Acad. Sci. Hung. 23, 179–195 (1972; Zbl 0247.05156)] gave a characterization of the saturated graphs called the cathedral theorem, with some applications to the enumeration problem of perfect matchings, and later Z. Szigeti [in: Integer programming and combinatorial optimization. Proceedings of a conference held at Centro Ettore Majorana, Erice, Italy, 1993. Louvain-la-Neuve: Librarian CORE, 413–423 (1993; Zbl 0920.05057); Eur. J. Comb. 22, No. 6, 865–877 (2001; Zbl 1050.05104)] 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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C27 Combinatorial optimization
05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv