Decomposing almost complete graphs by random trees

An old conjecture of Ringel states that every tree with m edges decomposes the complete graph Krm+1 for each r≥2 provided that r and m+1 are not both odd. The best lower bound for the order of a complete graph decomposed by a given tree with m edge is O(m3). We show that asymptotically almost surely a random tree with m edges and p=2m+1 a prime decomposes K2m+1(r) for every r≥2, the graph obtained from the complete graph K2m+1 by replacing each vertex by a coclique of order r.