Covering Cubic Graphs with 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.

Berg and independently Fulkerson fulker.htm
conjectured that every bridgeless cubic graph has a collection of six
perfect matchings that together contain every edge exactly twice. Any 5
of these 6 matchings contain every edge at least once.

**Conjecture:** *There exists a *k* such that every
bridgeless cubic graph has a collection of *k* perfect matchings
such that every edge is in at least one matching.
*

-- every bridgeless cubic graph has a collection of 5 perfect matchings such that every edge is in at least one matching, and

-- every bridgeless cubic graph has a collection of 6 perfect matchings such that every edge is in exactly two of them.

For a related problem see intmatch.html.

**References:**

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

[M] G. Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, to appear J. Graph Theory, to appear.

Submitted by: Dan Archdeacon, Department of Mathematics and
Statistics, University of Vermont, Burlington VT 05405 USA. (With
thanks to Matt Devos)

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

December 2003 (modified November 2010)