Cubic bridgeless graphs have more than a linear number of perfect matchings

Abstract

We prove the first superlinear bound on the number of perfect matchings in cubic bridgeless graphs.

Keywords

• Cubic
• bridgeless
• graphs
• linear
• number
• perfect
• matchings