Edge-decompositions of graphs with high minimum degree

Ben Barber, Daniela Kühn, Allan Lo, Deryk Osthus

Published 2014-10-21Version 1

A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here a graph $G$ is $F$-divisible if $e(F)$ divides $e(G)$ and the greatest common divisor of the degrees of $F$ divides the greatest common divisor of the degrees of $G$, and $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$. We extend this result to graphs which are allowed to be far from complete: our results imply that every sufficiently large $F$-divisible graph $G$ on $n$ vertices with minimum degree at least $(1- ( 9 |F|^{10})^{-1} +\epsilon)n$ has an $F$-decomposition. Moreover, every sufficiently large $K_3$-divisible graph of minimum degree $0.956n$ has a $K_3$-decomposition. Our result significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large $K_3$-divisible graph with minimum degree $3n/4$ has a $K_3$-decomposition. For certain graphs, we can strengthen the general bound above. In particular, we obtain the asymptotically correct threshold of $n/2+o(n)$ for even cycles of length at least 6. Our main contribution is a general method which turns an approximate decomposition into an exact one.