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.

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.

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