Successive minimum spanning trees

In a complete graphK nwith independent uniform ( 0 , 1 ) (or exponential ( 1 ) ) edge weights, letT 1be the minimum‐weight spanning tree (MST), andT kthe MST after deleting the edges of all previous trees. We show that each tree's weight w ( T k ) converges in probability to a constantγ k, with 2 k − 2 k < γ k < 2 k + 2 k, and we conjecture thatγ k = 2 k − 1 + o ( 1 ) . The problem is distinct from Frieze and Johansson's minimum combined weightμ kof k edge‐disjoint spanning trees; indeed,μ 2 < γ 1 + γ 2. With an edge of weight w “arriving” at time t = n w , Kruskal's algorithm defines forestsF k ( t ) , initially empty and eventually equal toT k, each edge added to the first possibleF k ( t ) . Using tools of inhomogeneous random graphs we obtain structural results including that the fraction of vertices in the largest component ofF k ( t ) converges to someρ k ( t ) . We conjecture that the functionsρ ktend to time translations of a single function.