An exact probability distribution on the connectivity of random graphs

Recently, several authors have proposed the use of random graph theory to evaluate the adequacy of cluster analysis results. One such statistic is the minimum number of lines (edges) V needed to connect a random graph. Erdös and Rényi derived asymptotic distributions of V. Schultz and Hubert showed in a Monte Carlo study that the asymptotic approximations are poor for small sample sizes n typically used in data analysis applications. In this paper the exact probability distribution of V is given and the distributions for some values of n are tabulated and compared with existing Monte Carlo approximations.