A multigraph is a graph in which two vertices are contained in more than one edge, but loops are not allowed. A set of edges is parallel if all of its edges contain the same two vertices. The size of the largest parallel set of edges is called the multiplicity of the graph. A simple graph has a multiplicity of one. The term “matching” refers to a set of edges such that no two edges contain a common vertex. A 1-factor is “a matching that covers every vertex.” A 1-factorization is a partition of the edge set into 1-factors.

The 1-factorization conjecture by Chetwynd and Hilton [1] states: “Any regular simple graph of order 2n and degree at least n is 1-factorizable.” Plantholt and Tipnis [2] formulated a natural generalization for multigraphs, stating that any regular multigraph of order 2n with multiplicity at most r and degree at least rn is 1-factorizable.

The author proves the following theorem: “For all positive integers r and all ϵ > 0, there is an integer N = N(r, ϵ) such that for all n ≥ N any regular multigraph of order 2n with multiplicity at most r and degree at least (1 + ϵ)rn is 1-factorizable.” This theorem is an interesting step toward the conjecture, as it already gives an asymptotic version.

The proof given by the author in this nicely written paper is self-contained and based on combinatorial techniques.