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.