A perfectly Hamiltonian graph is a regular graph that admits a perfect 1-factorization. A k-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.
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.
