Proof of the $1$-factorization and Hamilton Decomposition Conjectures

In this paper we prove the following results (via a unified approach) for all sufficiently large $n$: (i) [$1$-factorization conjecture] Suppose that $n$ is even and $D\geq 2\lceil n/4\rceil -1$\mathrm{.}Thenevery$D$-regulargraph$G$on$n$ vertices has a decomposition into perfect matchings. Equivalently, ${\chi }^{\mathrm{\prime }}(G)=D$. (ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2 \rfloor $\mathrm{.}Thenevery$D$-regulargraph$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 $\delta \ge n\mathrm{/}2$. Then $G$ contains at least ${\mathrm{r}\mathrm{e}\mathrm{g}}_{\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}}(n,\delta )\mathrm{/}2\ge (n-2)\mathrm{/}8$ edge-disjoint Hamilton cycles. Here ${\text{reg}}_{\text{even}}(n,\delta )$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $\delta$. (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case $\delta =\lceil n\mathrm{/}2\rceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.