Counting matchings in cubic graphs
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This bachelor thesis concerns the proof of Esperet et al. of the Lov ász-Plummer conjecture, which states that a cubic bridgeless graph has exponentially many perfect matchings. The first part of this thesis treats the concepts used in this proof. By means of examples, small proofs and a structural overview, this proof is made more accessible. The second part formulates and proofs a stronger version of one of the lemmas in the original proof. This results in an improved constant for the exponential lower bound of the number of perfect matchings.