A new lower bound on the number of perfect matchings in cubic graphs

Abstract

We prove the first lower bound on the number of perfect matchings of cubic bridgeless graphs not based on the dimension of the perfect matchings polytope.

Keywords

• perfect matchings
• number of perfect matchings
• cubic graphs