The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

Abstract

Abstract The minimal weight of a spanning tree in a complete graph K n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.