An old conjecture of Ringel states that every tree with m edges decomposes the complete graph Krm+1Krm+1 for each r=2r=2 provided that r and m+1m+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)O(m3). We show that asymptotically almost surely a random tree with m edges and p=2m+1p=2m+1 a prime decomposes K2m+1(r)K2m+1(r) for every r=2r=2, the graph obtained from the complete graph K2m+1K2m+1 by replacing each vertex by a c...
An old conjecture of Ringel states that every tree with m edges decomposes the complete graph Krm+1Krm+1 for each r=2r=2 provided that r and m+1m+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)O(m3). We show that asymptotically almost surely a random tree with m edges and p=2m+1p=2m+1 a prime decomposes K2m+1(r)K2m+1(r) for every r=2r=2, the graph obtained from the complete graph K2m+1K2m+1 by replacing each vertex by a coclique of order r.