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

Abstract

Let T be a tree with m edges. A well-known conjecture of Ringel states that every tree T with m edges decomposes the complete graph K2m+1. Graham and H¨aggkvist conjectured that T also decomposes the complete bipartite graph Km,m. In this paper, we show that there exists an integer n with n  d3(m 1)/2e and a tree T1 with n edges such that T1 decomposes K2n+1 and contains T. We also show that there exists an integer n0 with n0 2m 1 and a tree T2 with n0 edges such that T2 decomposes Kn0,n0 . In the latter case, we can improve the bound if there exists a prime p such that d3m/2e  p  2m 1.

This work was supported by the Ministry of Science and Education of Spain under project MTM2005-08990-C02-01 and by the Catalan Research Council under grant 2005SGR00256.