Perfect Matchings in Cubic Graphs that have Empty Intersection

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. No
edge is in three of these matchings.

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

For a related problem see covmatch.html.

**References:**

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

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