Alspach's conjecture is a mathematical theorem that characterizes the disjoint cycle covers of complete graphs with prescribed cycle lengths.
It is named after Brian Alspach, who posed it as a research problem in 1981.
A proof was published by Darryn Bryant, Daniel Horsley, and William Pettersson (2014).
In this context, a disjoint cycle cover is a set of simple cycles, no two of which use the same edge, that include all of the edges of a graph.
Alspach conjectured that, for complete graphs, these two necessary conditions are also sufficient: if
is odd (so that the degrees are even) and a given list of cycle lengths (all at most
It is this statement that Bryant, Horsley, and Pettersson proved.
of vertices is even, Alspach conjectured that it is always possible to decompose the graph into a perfect matching and a collection of cycles of prescribed lengths summing to
In this case the matching eliminates the odd degree at each vertex, leaving a subgraph of even degree, and the remaining condition is again that the sum of the cycle lengths equals the number of edges to be covered.
This variant of the conjecture was also proven by Bryant, Horsley, and Pettersson.
The Oberwolfach problem on decompositions of complete graphs into copies of a given 2-regular graph is related, but neither is a special case of the other.
vertices, formed from a disjoint union of cycles of certain lengths, then a solution to the Oberwolfach problem for
, and on the other hand not every instance of Alspach's conjecture involves sets of cycles that have