Counting matchings in cubic graphs
P.J. Otte · Research Repository (Delft University of Technology) · 2014
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.