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.
In simpler terms, 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) has posed the question if the Grabarchuk graph (and other sextic graphs that have many Hamiltonian cycles) are perfectly Hamiltonian.
