In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs.
In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.
For a Hamiltonian decomposition to exist in an undirected graph, the graph must be connected and regular of even degree.
A directed graph with such a decomposition must be strongly connected and all vertices must have the same in-degree and out-degree as each other, but this degree does not need to be even.
Special classes of graphs
Every complete graph with an odd number n of vertices has a Hamiltonian decomposition. This result, which is a special case of the Oberwolfach problem of decomposing complete graphs into isom