An alternative proof of Lovász's cathedral theorem

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)15-34
Number of pages20
JournalJournal of the Operations Research Society of Japan
Volume57
Issue number1
DOIs
Publication statusPublished - Mar 2014

Keywords

  • Combinatorial optimization
  • Graph theory
  • Matching theory
  • Perfect matchings
  • The cathedral theorem

Fingerprint Dive into the research topics of 'An alternative proof of Lovász's cathedral theorem'. Together they form a unique fingerprint.

  • Cite this