Decomposing large graphs with small graphs of high density

It is shown that for every positive integer h, and for every ϵ > 0, there are graphs H = )V_H E_H) with at least h vertices and with density at least 0.5 - ϵ with the following property: If G = (V_G, E_G) is any graph with minimum degree at least (1 + o(1)) and |E_H| divides |E_G|, then G has an H-decomposition. This result extends the results of R. M. Wilson, Cong Numer XV (1925), 647–659] T. Gustavsson, Ph.D. Thesis, U. Stockholm, 1991] R. Yuster, Random Struc Algorith, 12 (1998), 237–251]. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 27–40, 1999