Every tree is a large subtree of a tree that decomposes KnKn or Kn,nKn,n

Let TT be a tree with mm edges. A well-known conjecture of Ringel states that TT decomposes the complete graph K2m+1K2m+1. Graham and Häggkvist conjectured that TT also decomposes the complete bipartite graph Km,mKm,m. In this paper we show that there exists an integer nn with n≤⌈(3m−1)/2⌉n≤⌈(3m−1)/2⌉ and a tree T1T1 with nn edges such that T1T1 decomposes K2n+1K2n+1 and contains TT. We also show that there exists an integer n′n′ with n′≥2m−1n′≥2m−1 and a tree T2T2 with n′n′ edges such that T2T2 decomposes Kn′,n′Kn′,n′ and contains TT. In the latter case, we can improve the bound if there exists a prime pp such that ⌈3m/2⌉≤p<2m−1⌈3m/2⌉≤p<2m−1.