The expected value of random minimal length spanning tree of a complete graph

Abstract

We consider the number c(n, m) of connected labeled graphs on n nodes and m edges and the intimately related object, the expected length of the minimal spanning tree of a complete graphs with random edge lengths. We use a very simple recursive procedure for computing the values of c(n, m) for computing the expected length of the minimal spanning tree exactly, under the uniform and the exponential distributions. Our computations are recursive, scale very well with the size of the problem, and we provide the values of the expected minimal length spanning trees for complete graphs K n with sizes n ≤ 45, extending recent results of Steele [Ste02], and Fill and Steele [FS04]. The main proof technique is based on introducing an artificial root to a graph and subsequently using a very simple inductive argument.