![](/files/happy5.png)
perfect matching
Exponentially many perfect matchings in cubic graphs ★★★
Conjecture There exists a fixed constant
so that every
-vertex cubic graph without a cut-edge has at least
perfect matchings.
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ e^{cn} $](/files/tex/22656fabb8498ada6bf54e6068c4978436afcc8f.png)
Keywords: cubic; perfect matching
The intersection of two perfect matchings ★★
Conjecture Every bridgeless cubic graph has two perfect matchings
,
so that
does not contain an odd edge-cut.
![$ M_1 $](/files/tex/6053a26729abbb4d69de99ccd5976244ef2773c9.png)
![$ M_2 $](/files/tex/b0ecd935059283a5c903e8bbf8faf28490053d61.png)
![$ M_1 \cap M_2 $](/files/tex/15325788d4a123d31609b6e498c31ecaca4b6f19.png)
Keywords: cubic; nowhere-zero flow; perfect matching
The Berge-Fulkerson conjecture ★★★★
Conjecture If
is a bridgeless cubic graph, then there exist 6 perfect matchings
of
with the property that every edge of
is contained in exactly two of
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ M_1,\ldots,M_6 $](/files/tex/8ab42e6cd40fd3556882bbb8216d0b8e14f3bf3e.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ M_1,\ldots,M_6 $](/files/tex/8ab42e6cd40fd3556882bbb8216d0b8e14f3bf3e.png)
Keywords: cubic; perfect matching
![Syndicate content Syndicate content](/misc/feed.png)