Plummer, Michael D.


Exponentially many perfect matchings in cubic graphs ★★★

Author(s): Lovasz; Plummer

\begin{conjecture} There exists a fixed constant $c$ so that every $n$-vertex cubic graph without a cut-edge has at least $e^{cn}$ perfect matchings. \end{conjecture}

Keywords: cubic; perfect matching

Syndicate content