![](/files/happy5.png)
Matchings
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
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
Matchings extend to Hamiltonian cycles in hypercubes ★★
Keywords: Hamiltonian cycle; hypercube; matching
Random stable roommates ★★
Author(s): Mertens
Conjecture The probability that a random instance of the stable roommates problem on
people admits a solution is
.
![$ n \in 2{\mathbb N} $](/files/tex/9d83db49a5d584edf4769392d3727c2df30f50c1.png)
![$ \Theta( n ^{-1/4} ) $](/files/tex/7d356e001ed3a6d5303d583183ae3cbba921cbec.png)
Keywords: stable marriage; stable roommates
![Syndicate content Syndicate content](/misc/feed.png)