Exponentially many perfect matchings in cubic graphs

By Louis Esperet, Frantisek Kardos, Andrew D. King, Daniel Král', Sergey Norin. 2010

63 citations recorded by the source corpus.

We show that every cubic bridgeless graph G has at least 2|V(G)|/3656 perfect matchings. This confirms an old conjecture of Lovasz and Plummer.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/3d7abb8bde1ce33e3fc2e0a01b2678f50c2be328