Exponentially many perfect matchings in cubic graphs

Abstrakt

We prove a conjecture of Lovasz and Plummer that every cubic bridgeless graph contains an exponential number of perfect matchings.

Klíčová slova

• cubic bridgeless graph
• perfect matchings
• number of perfect matchings