vertices are connected. In random graphs, the algebraic connectivity decreases with the number of vertices, and increases with the average degree.

The exact definition of the algebraic connectivity depends on the type of Laplacian used. Fan Chung has developed an extensive theory using a rescaled version of the Laplacian, eliminating the dependence on the number of vertices, so that the bounds are somewhat different.