Packing and Decomposition of Graphs with Trees

AbstractLet H be a tree on h⩾2 vertices. It is shown that if n is sufficiently large and G=(V, E) is an n-vertex graph with δ(G)⩾⌊n/2⌋, then there are ⌊|E|/(h−1)⌋ edge-disjoint subgraphs of G which are isomorphic to H. In particular, if h−1 divides |E| then there is an H-decomposition of G. This result is best possible as there are infinitely many examples of trees on h vertices and graphs G with m(h−1) edges, δ(G)⩾⌊n/2⌋−1, for which G has no H-decomposition