  An old conjecture of Ringel states that every tree with $m$ edges decomposes
the complete graph $K_{2m+1}$. The best known lower bound for the order of a
complete graph which admits a decomposition by every given tree with $m$ edges
is $O(m^3)$. We show that asymptotically almost surely a random tree with $m$
edges and $p=2m+1$ a prime decomposes $K_{2m+1}(r)$ for every $r\ge 2$, the
graph obtained from the complete graph $K_{2m+1}$ by replacing each vertex by a
coclique of order $r$. Based on this result we show, among other results, that
a random tree with $m+1$ edges a.a.s. decomposes the compete graph $K_{6m+5}$
minus one edge.
