The asymptotic number of labeled connected graphs with a given number of vertices and edges
Edward A. Bender, E. Rodney Canfield, Brendan D. McKay · Random Structures and Algorithms · 1990
Abstract Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n) edges. Let x = q/n and k = q − n. We determine functions wk ˜ 1. a(x) and φ(x) such that c(n, q) ˜ wk(qN)enφ(x)+a(x) uniformly for all n and q ≥ n. If ϵ > 0 is fixed, n→ ∞ and 4q > (1 + ϵ)n log n, this formula simplifies to c(n, q) ˜ (Nq) exp(–ne−2q/n). on the other hand, if k = o(n1/2), this formula simplifies to c(n, n + k) ˜ 1/2 wk (3/π)1/2 (e/12k)k/2nn−(3k−1)/2.