Exponentially many perfect matchings in cubic graphs

Abstract

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. This version of the paper uses a different definition of a burl from the journal version of the paper and a different proof of Lemma 18 is given. This simplifies the exposition of our arguments throughout the whole paper.

References in corpus (3)

• Exponentially many perfect matchings in cubic graphs
• An improved linear bound on the number of perfect matchings in cubic graphs
• A superlinear bound on the number of perfect matchings in cubic bridgeless graphs

Cited by in corpus (19)

• Exponentially many perfect matchings in cubic graphs
• Perfect Matchings in Claw-free Cubic Graphs
• Sandwiching saturation number of fullerene graphs
• Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
• An equivalent formulation of the Fan-Raspaud Conjecture and related problems
• Avoiding 5-circuits in a 2-factor of cubic graphs
• A bound for the number of vertices of a polytope with applications
• Analogs of the van der Waerden and Tverberg conjectures for haffnians
• On the expected number of perfect matchings in cubic planar graphs
• A Cohomology Theory for Planar Trivalent Graphs with Perfect Matchings
• Connected cubic graphs with the maximum number of perfect matchings
• Nice vertices in cubic graphs
• Three-cuts are a charm: acyclicity in 3-connected cubic graphs
• Non-degenerated groundstates in the antiferromagnetic Ising model on triangulations
• Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
• Computing the partition function for perfect matchings in a hypergraph
• Computational Hardness of Enumerating Satisfying Spin-Assignments in Triangulations
• Exponentially many nowhere-zero $Z_3$-, $Z_4$-, and $Z_6$-flows
• Solvability of Cubic Graphs - From Four Color Theorem to NP-Complete