Tail bound for the minimal spanning tree of a complete graph

Suppose each edge of the complete graph Kn is assigned a random weight chosen independently and uniformly from the unit interval [0,1]. A minimal spanning tree is a spanning tree of Kn with the minimum weight. It is easy to show that such a tree is unique almost surely. This paper concerns the number Nn([alpha]) of vertices of degree [alpha] in the minimal spanning tree of Kn. For a positive integer [alpha], Aldous (Random Struct. Algorithms 1 (1990) 383) proved that the expectation of Nn([alpha]) is asymptotically [gamma]([alpha])n, where [gamma]([alpha]) is a function of [alpha] given by explicit integrations. We develop an algorithm to generate the minimal spanning tree and Chernoff-type tail bound for Nn([alpha]).Minimal spanning tree Large deviation Martingale inequality