The number of connected sparsely edged graphs. III. Asymptotic results

Abstract

Abstract The number of connected graphs on n labeled points and q lines (no loops, no multiple lines) is f(n,q). In the first paper of this series I showed how to find an (increasingly complicated) exact formula for f(n,n+k) for general n and successive k. The method would give an asymptotic approximation to f(n,n+k) for any fixed k as n → ∞. Here I find this approximation when k = o(n 1/3 ), a much more difficult matter. The problem of finding an approximation to f(n,q) when q > n + Cn 1/3 and (2 q/n ) ‐ log n → ‐ ∞ is open.