Double Covering Edges by Perfect Matchings

A *perfect matching* or *1-factor* in a graph is a
collection of edges which together are incident with every vertex
exactly once. A *1-factorization* is a partition of the edges
into 1-factors. If the graph is regular of degree *d*, then a
1-factorization is equivalent to a proper edge *d*-coloring. A *cubic*
graph is one that is regular of degree three.

Not every cubic graph can be edge-partitioned into perfect matchings. The Petersen graph is a counterexample. The following was conjectured (I believe independently) by Berge and by Fulkerson. I've heard it called the Berge-Fulkerson conjecture, but more frequently just Fulkerson's Conjecture (who I believe was the first to publish it).

**Conjecture:** *Every bridgeless cubic graph has a collection
of six perfect matchings together contain every edge exactly twice.*

The Petersen graph is not a counterexample (so the conjecture must be true!); the six 1-factors form such a double cover. Note that any 3-edge-colorable cubic graph (Class 1) 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. An extension of this would allow 1-factors of arbitrary rational weight. Another variation would be to allow adding or subtracting 1-factors. I believe that these variations may be known.

Mike Albertson asks if the conjecture is easier for toroidal graphs. He can show that there are 7 matchings together containing every edge exactly twice. He asks if there are 3 matchings that collectively cover all but two edges in a bridgeless 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. In my opinion this is one of the most important open problems in the field.

A dual problem is called the Cycle double
cover conjecture. For relaxations see Covering
cubic graphs with perfect matchings and Perfect
matchings in cubic graphs that have empty intersection

**References:**

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

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

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.

Send comments to *dan.archdeacon@uvm.edu
*

August 1995, modified December 2003