← Problem set
Matching theory · posed 1971
The Berge–Fulkerson Conjecture
Every bridgeless cubic graph has six perfect matchings arranged so that every edge lies in exactly two of them.
Formal statement
Obstruction
Why the direct approaches fail
The conjecture implies the Fan–Raspaud statement that every bridgeless cubic graph has three perfect matchings with empty common intersection — itself open — so any proof must clear that lower bar first. The Petersen graph is the tight extremal case, and general snarks defeat every known matching-covering argument; even bounding the number of perfect matchings needed to cover all edges by any constant was hard-won.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Prove the weaker Fan–Raspaud conjecture (three matchings, empty intersection) as a stepping stone.
- 02Verify the six-matching cover for all snarks of small order and extract a structural invariant.
- 03Connect the conjecture to nowhere-zero flows and isolate the Petersen graph as the unique obstruction.
- 04Bound the fractional relaxation and quantify the integrality gap on cyclically 4-edge-connected graphs.
Under attack now
Berge–Fulkerson has its own lane in the solver, running continuously alongside every other problem.