On the number of leaves of a euclidean minimal spanning tree

Abstract

Let V k,n be the number of vertices of degree k in the Euclidean minimal spanning tree of X i , , where the X i are independent, absolutely continuous random variables with values in R d . It is proved that n –1 V k,n converges with probability 1 to a constant α k,d . Intermediate results provide information about how the vertex degrees of a minimal spanning tree change as points are added or deleted, about the decomposition of minimal spanning trees into probabilistically similar trees, and about the mean and variance of V k,n .