Successive minimum spanning trees

In a complete graph Kn with independent uniform(0; 1)(or exponential(1)) edge weights, let T1 be the MST (minimum-weight spanning tree), and Tk the MST after deleting the edges of all previous trees. We show that each tree's weight w(Tk) converges in probability to a constant k, with 2k &#x100000;2pk < k < 2k +2pk, and we conjecture that k = 2k&#x100000;1+o(1). The problem is distinct from Frieze and Johansson's minimum combined weight k of k edge-disjoint spanning trees; indeed,2 < 1 + 2.With an edge of weight w \arriving" at time t = nw, Kruskal's algorithm denes forests Fk(t), initially empty and eventually equal to Tk, each edge added to the rst possible Fk(t). Using tools of inhomogeneous random graphs we obtain structural results including that the fraction of vertices in the largest component of Fk(t) converges to some k(t). We conjecture that the functions k tend to time translations of a single function.