A 
-factor
of a graph is a spanning 
-regular subgraph of the original graph. The special case of
a 1-factor is precisely a perfect matching. A
1-factorization of a graph is a partition of its edge set
into 1-factors. A pair of 1-factors whose union forms a Hamiltonian
cycle is said to be a perfect set of 1-factors, and a 1-factorization is said
to be perfect if all pairs of its 1-factors are perfect.
A regular graph of vertex degree 
is then called a perfectly Hamiltonian graph if it admits a perfect 1-factorization.
Equivalently, an 
-regular graph is perfectly Hamiltonian if its edges can be
-colored
in such a way that all 
pairs of colors yield Hamiltonian
cycles (Knuth 2025, solution to Problem 24). Perfectly Hamiltonian graphs therefore
automatically admit a Hamilton decomposition.
The term "perfectly Hamiltonian" was suggested by D. Knuth (pers. comm. to van Cleemput and Zamfirescu, Sep. 2019; Knuth 2025). Kotzig and Labelle (1979) called such graphs "fortement hamiltonien" (van Cleemput and Zamfirescu 2022).
Every cubic graph containing exactly three Hamiltonian cycles is perfectly Hamiltonian (van Cleemput and Zamfirescu 2022). However, planar cubic perfectly Hamiltonian graphs with more than three Hamiltonian cycles also exist, an example of which is the dodecahedral graph (van Cleemput and Zamfirescu 2022).
D. Knuth (pers. comm., Jul. 22, 2025) asked whether sextic graphs having many Hamiltonian cycles are
necessarily perfectly Hamiltonian. A theorem due to Kotzig (1958) gives a general
obstruction in the bipartite case: no bipartite 
-regular graph with bipartition classes of even cardinality
and 
can be perfectly Hamiltonian (Kotzig 1958, Kotzig and Labelle 1979). To see this,
let the two bipartition classes be 
and 
, with 
, and identify every 1-factor 
with the corresponding bijection 
. For two 1-factors 
and 
, the alternating cycles in 
correspond to the cycles of the permutation 
on 
; hence 
is a Hamiltonian
cycle iff 
is a single 
-cycle. After fixing orderings of 
and 
, if 
is even, such a cycle is an odd permutation, so every pair
of 1-factors in a perfect 1-factorization would have to have opposite permutation
parity. This is impossible for 
, since there are only two parities.
Note that this obstruction does not apply to all sextic graphs. For example, the 16-cell graph is sextic and perfectly Hamiltonian, but it has only 744 Hamiltonian cycles.
