Proof of the 1-factorization and Hamilton Decomposition Conjectures

Source abstract

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\geq 2\lceil n/4\rceil -1 . Then every D D -regular graph G G on n n vertices has a decomposition into perfect matchings. Equivalently, χ ′ ( G ) = D \chi ’(G)=D . [ Hamilton decomposition conjecture ] Suppose that D ≥ ⌊ n / 2 ⌋ D \ge \lfloor n/2 \rfloor . 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 vertices with minimum degree δ ≥ n / 2 \delta \ge n/2 . Then G G contains at least reg even ( n , δ ) / 2 ≥ ( n − 2 ) / 8 \textrm {reg}_\textrm {even}(n,\delta )/2 \ge (n-2)/8 edge-disjoint Hamilton cycles. Here r e g e v e n ( n , δ ) \mathrm {reg}_{\mathrm {even}}(n,\delta ) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n n vertices with minimum degree δ \delta . (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case δ = ⌈ n / 2 ⌉ \delta = \lceil n/2 \rceil of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.