  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\geq 2\lceil
n/4\rceil -1$. Then every $D$-regular graph $G$ on $n$ vertices has a
decomposition into perfect matchings. Equivalently, $\chi'(G)=D$.
  (ii) [Hamilton decomposition conjecture] Suppose that $D \ge \lfloor n/2
\rfloor $. 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 show the following: suppose that $G$ is close to a
complete balanced bipartite graph or to the union of two cliques of equal size.
If we are given a suitable set of path systems which cover a set of
`exceptional' vertices and edges of $G$, then we can extend these path systems
into an approximate decomposition of $G$ into Hamilton cycles (or perfect
matchings if appropriate).
