Hamiltonian decomposition

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 such a decomposition to exist in an undirected graph, it 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.

It is known that every complete graph with an odd number ${\displaystyle n}$ of vertices has a Hamiltonian decomposition. This result, which is a special case of the Oberwolfach problem of decomposing complete graphs into isomorphic 2-factors, was attributed to Walecki by Édouard Lucas in 1892. Walecki's construction places ${\displaystyle n-1}$ of the vertices into a regular polygon, and covers the complete graph in this subset of vertices with ${\displaystyle (n-1)/2}$ Hamiltonian paths that zigzag across the polygon, with each path rotated from each other path by a multiple of ${\displaystyle \pi /(n-1)}$. The paths can then all be completed to Hamiltonian cycles by connecting their ends through the remaining vertex.

...
Wikipedia