Packing Trees in Complete Bipartite Graphs

An embedding of a graph H in a graph G is an injection (i.e., a one-to-one function) σ from the vertices of H to the vertices of G such that σ(x)σ(y) is an edge of G for all edges xy of H. The image of H in G under σ is denoted by σ(H). A k-packing of a graph H in a graph G is a sequence (σ₁, σ₂,…, σ_k) of embeddings of H in G such that σ₁(H), σ₂(H),…, σ_k(H) are edge disjoint. We prove that for any tree T of order n, there is a 4-packing of T in a complete bipartite graph of order at most n+12.