In graph theory, a cycle decomposition is a decomposition (a partitioning of a graph's edges) into cycles.
Every vertex in a graph that has a cycle decomposition must have even degree.
Brian Alspach and Heather Gavlas established necessary and sufficient conditions for the existence of a decomposition of a complete graph of even order minus a 1-factor (a perfect matching) into even cycles and a complete graph of odd order into odd cycles.
[1] Their proof relies on Cayley graphs, in particular, circulant graphs, and many of their decompositions come from the action of a permutation on a fixed subgraph.
They proved that for positive even integers
is a 1-factor) can be decomposed into cycles of length
if and only if the number of edges in
Also, for positive odd integers
can be decomposed into cycles of length
This graph theory-related article is a stub.