The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c ( n, q ) be the number of connected labeled graphs with n vertices and q ≤ N = (2 n ) edges. Let x = q/n and k = q − n . We determine functions w k ˜ 1. a ( x ) and φ( x ) such that c ( n, q ) ˜ w k ( q N ) e n φ ( x )+ a ( x ) uniformly for all n and q ≥ n . If ϵ > 0 is fixed, n → ∞ and 4 q > (1 + ϵ) n log n , this formula simplifies to c ( n, q ) ˜ ( N q ) exp(– ne −2 q/n ). on the other hand, if k = o ( n 1/2 ), this formula simplifies to c ( n, n + k ) ˜ 1/2 w k (3/π) 1/2 ( e /12 k ) k /2 n n − (3 k −1)/2 .