5.3.3. Hamiltonian factorization

We turn on the problem whether there exists a factorization of a graph such that every factor is a single cycle (2-factor) ?

A hamiltonian factorization of a graph is a factorization such that every factor is a hamiltonian cycle of G.

Theorem 5.8. For every positive integer k, the graph  is hamiltonian factorable.

Proof.

The result is obvious for . So we assume that .

Let  and arrange the vertices  in a regular 2k-gon, placing  in a convenient position.

Join every two vertices by a straight line segment, producing .

For , define the 1-factor  to consist of the edge , all edges parallel to  and all edges parallel to , where the subscript are expressed modulo 2k.

Then , so  is 1-factorable.

Consequence 5.9. The complete graph  can be factored into k hamiltonian paths.