  We prove that for every complete multipartite graph $F$ there exist very
dense graphs $G_n$ on $n$ vertices, namely with as many as ${n\choose 2}-cn$
edges for all $n$, for some constant $c=c(F)$, such that $G_n$ can be
decomposed into edge-disjoint induced subgraphs isomorphic to~$F$. This result
identifies and structurally explains a gap between the growth rates $O(n)$ and
$\Omega(n^{3/2})$ on the minimum number of non-edges in graphs admitting an
induced $F$-decomposition.
