## 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.

**
****References:**

[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 Bojan.Mohar@uni-lj.si

##### Revised: oktober 24, 2001.