Kita, Nanao An alternative proof of Lovász’s cathedral theorem. (English) Zbl 1301.05264 J. Oper. Res. Soc. Japan 57, No. 1, 15-34 (2014). 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. Cited in 2 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 90C27 Combinatorial optimization 05C30 Enumeration in graph theory Keywords:combinatorial optimization; matching theory; perfect matchings; cathedral theorem Citations:Zbl 0247.05156; Zbl 0920.05057; Zbl 1050.05104 PDFBibTeX XMLCite \textit{N. Kita}, J. Oper. Res. Soc. Japan 57, No. 1, 15--34 (2014; Zbl 1301.05264) Full Text: DOI arXiv