Cycle decomposition (graph theory)
In graph theory, a cycle decomposition is a decomposition into cycles. Every vertex in a graph that has a cycle decomposition must have even degree.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 into even cycles and a complete graph of odd order into odd cycles. 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 and with, the graph can be decomposed into cycles of length if and only if the number of edges in is a multiple of. Also, for positive odd integers and with 3≤m≤n, the graph can be decomposed into cycles of length if and only if the number of edges in is a multiple of.
