Alspach's conjecture is a
mathematical theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of the ...
that characterizes the
disjoint cycle covers of
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
s with prescribed cycle lengths. It is named after
Brian Alspach, who posed it as a research problem in 1981. A proof was published by .
Formulation
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. For a disjoint cycle cover to exist, it is necessary for every vertex to have even
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
, because the degree of each vertex is two times the number of cycles that include that vertex, an even number. And for the cycles in a disjoint cycle cover to have a given collection of lengths,
it is also necessary for the sum of the given cycle lengths to equal the total number of edges in the given 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
) adds to
(the number of edges in the complete graph) then the complete graph
can always be decomposed into cycles of the given length. It is this statement that Bryant, Horsley, and Pettersson proved.
Generalization to even numbers of vertices
For complete graphs
whose number
of vertices is even, Alspach conjectured that it is always possible to decompose the graph into a
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
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.
Related problems
The
Oberwolfach problem
The Oberwolfach problem is an unsolved problem in mathematics that may be formulated either as a problem of scheduling seating assignments for diners,
or more abstractly as a problem in graph theory, on the edge cycle covers of complete graphs. I ...
on decompositions of complete graphs into copies of a given 2-regular graph is related, but neither is a special case of the other.
If
is a 2-regular graph, with
vertices, formed from a disjoint union of cycles of certain lengths, then a solution to the Oberwolfach problem for
would also provide a decomposition of the complete graph into
copies of each of the cycles of
. However, not every decomposition of
into this many cycles of each size can be grouped into disjoint cycles that form copies of
, and on the other hand not every instance of Alspach's conjecture involves sets of cycles that have
copies of each cycle.
References
*
*
*{{citation
, last1 = Chartrand , first1 = Gary , author1-link = Gary Chartrand
, last2 = Lesniak , first2 = Linda
, last3 = Zhang , first3 = Ping , author3-link = Ping Zhang (graph theorist)
, contribution = Alspach's conjecture
, contribution-url = https://books.google.com/books?id=Cjw0CwAAQBAJ&pg=PA349
, edition = 6th
, isbn = 9781498735803
, page = 349
, publisher = CRC Press
, series = Textbooks in Mathematics
, title = Graphs & Digraphs
, volume = 39
, year = 2015
Theorems in graph theory
Conjectures that have been proved