Proof of the 1-Factorization and Hamilton Decomposition Conjectures

In this paper the authors prove the following results for all sufficiently large $n$: [$1$-factorization conjecture] Suppose that $n$ is even and $D/geq 2/lceil n/4/rceil -1$; [Hamilton decomposition conjecture] Suppose that $D /ge /lfloor n/2 /rfloor $; [Optimal packings of Hamilton cycles] Suppose that $G$ is a graph on $n$ vertices with minimum degree $/delta/ge n/2$.

---

In this paper the authors prove the following results (via a unified approach) for all sufficiently large n:

(i) [1-factorization conjecture] Suppose that n is even and D≥2⌈n/4⌉−1. Then every D-regular graph G on n vertices has a decomposition into perfect matchings. Equivalently, χ′(G)=D.

(ii) [Hamilton decomposition conjecture] Suppose that D≥⌊n/2⌋. Then every D-regular graph G on n vertices has a decomposition into Hamilton cycles and at most one perfect matching.

(iii) [Optimal packings of Hamilton cycles] Suppose that G is a graph on n vertices with minimum degree δ≥n/2. Then G contains at least regeven (n,δ)/2≥(n−2)/8 edge-disjoint Hamilton cycles. Here regeven (n,δ) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree δ.

(i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case δ=⌈n/2⌉of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.