Berge-Fulkerson Conjecture

Conjecture (Berge and Fulkerson): Every 2-connected cubic graph has a collection of six perfect matchings that together cover every edge exactly twice.

This conjecture is attributed to Berge in [2]. The first printed appearance is in [1].

A good indication that this conjecture might be true is that the Petersen graph is not a counterexample. Note that every 3-edge-colorable cubic graph trivially satisfies the conjecture.

The problem can also be phrased as a fractional edge coloring. That is, each edge receives two ``half colors'' so that no half color is repeated at a vertex.

Mike Albertson asked if the conjecture is easier for toroidal graphs. He can show that there are 7 matchings together containing every edge exactly twice. He asked if there are 3 matchings that collectively cover all but two edges in a 2-connected toroidal cubic graph.

Archdeacon, Bonnington, and Siran (unpublished work) have examined many non-3-edge-colorable graphs of small order and have verified that they satisify the conjecture.

The following weaker version of the conjecture is also due to Berge (unpublished):

Conjecture (Berge): Every 2-connected cubic graph has a collection of five perfect matchings that together cover all edges of the graph.

The famous Cycle double cover conjecture can be viewed as a dual to the Berge-Fulkerson Conjecture.


[1] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194.

[2] P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. (3) 38 (1979) 423-460. 

Send comments to

Revised: oktober 24, 2001.