PROOF OF THE 1-FACTORIZATION AND HAMILTON DECOMPOSITION CONJECTURES IV: EXCEPTIONAL SYSTEMS FOR THE TWO CLIQUES CASE

Abstract. In a sequence of four papers, 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 ≥ 2dn/4e − 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 ≥ bn/2c. Then every D-regular graph G on n vertices has a decomposition into Hamilton cycles and at most one perfect matching. (iii) We prove an optimal result on the number of edge-disjoint Hamilton cycles in a graph of given minimum degree. According to Dirac, (i) was first raised in the 1950s. (ii) and (iii) answer questions of Nash-Williams from 1970. The above bounds are best possible. In the current paper, we prove results on the decomposition of sparse graphs into path systems. These are used in the proof of (i) and (ii) in the case when G is close to the union of two disjoint cliques. 1