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 n : [ 1 1 -factorization conjecture ] Suppose that n n is even and D ≥ 2 ⌈ n / 4 ⌉ − 1 D≥ 2 n/4 -1 . Then every D D -regular graph G G on n n vertices has a decomposition into perfect matchings. Equivalently, χ ′ ( G ) = D χ ’(G)=D . [ Hamilton decomposition conjecture ] Suppose that D ≥ ⌊ n / 2 ⌋ D ≥ n/2 . Then every D D -regular graph G G on n n vertices has a decomposition into Hamilton cycles and at most one perfect matching. [ Optimal packings of Hamilton cycles ] Suppose that G G is a graph on n n