Math Conjectures

Berge–Fulkerson Conjecture

OPENLandmarkConjectureProposed 1971–1972 · Standard version

Canonical statement

Every finite bridgeless cubic loopless multigraph GG has six perfect matchings M1,…,M6M_1,\ldots,M_6, repetitions allowed, such that every edge of GG belongs to exactly two of the MiM_i.
View source LaTeX
Every finite bridgeless cubic loopless multigraph \(G\)
has six perfect matchings \(M_1,\ldots,M_6\), repetitions allowed, such
that every edge of \(G\) belongs to exactly two of the \(M_i\).
GRAPH-004:[Fulkerson1971Blocking][Mazzuoccolo2013Berge][Mkrtchyan2025Oriented]
Graph theoryOperations research

Notes

The Berge–Fulkerson conjecture asserts that every bridgeless cubic graph has six perfect matchings, repetitions allowed, such that every edge lies in exactly two of them; equivalently, doubling every edge yields a 66-edge-colorable multigraph. It appeared in Fulkerson's 1971 work on blocking and anti-blocking pairs of polyhedra [Fulkerson1971Blocking], with a closely related formulation associated with Berge, which accounts for the 1971–1972 dating.

For 33-edge-colorable cubic graphs the statement is immediate, since one may take each color class twice, so the difficulty is concentrated on snarks. The conjecture is known to hold for several major subclasses and is equivalent to natural covering formulations; in particular, Mazzuoccolo showed that Berge's conjecture, that five perfect matchings suffice to cover all edges of a bridgeless cubic graph, is equivalent to the full Berge–Fulkerson statement [Mazzuoccolo2013Berge]. An oriented version of the conjecture has also been proposed [Mkrtchyan2025Oriented].

A proof must produce the six-matching double cover without any recourse to 33-edge-colorability, and for general snarks the conjecture remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.