Asymptotic number of connected simple graphs of $n$ labelled vertices

graph theoryreference-request

Denote the number of connected graphs of $n$ labelled vertices by $d_n$. Then, as per How to calculate the number of possible connected simple graphs with n
labelled vertices
we have the recurrence
$$
\sum_k \binom{n}{k} k d_k 2^{\binom{n-k}{2}} = n 2^{\binom{n}{2}}.
$$
I am looking for an asymptotic formula (or just an asymptotic upper bound) for the sequence $d_n$.

Remarks

  • In The asymptotic number of labeled connected graphs with a given number of vertices and edges an asymptotic formula is found for the number of graphs with $n$ labelled vertices and $k$ edges. In principle one could then sum over $k$, but the formula is complicated and this does not seem feasible.
  • In generatingfunctionology by H. S. Wilf, Theorem 3.12.1 (downloadable here) the number of labelled trees of $n$ vertices is shown to be $n^{n-2}$, so at least $d_n\geq n^{n-2}$, but how much larger?

Best Answer

The simplest possible asymptotic formula is $d_n \sim 2^{\binom n2}$: almost all of the $2^{\binom n2}$ possible graphs are connected.

To prove this, and get some more precise estimates, we can look at how a disconnected graph can happen.

  • The simplest way is to have an isolated vertex. There are $n d_{n-1}$ graphs which are connected except for an isolated vertex. This is at most $n 2^{\binom{n-1}{2}}$, since $d_{n-1}$ is at most the total number of $(n-1)$-vertex graphs.
  • In all other cases of disconnected graphs, we can partition the vertex set into two parts $(S,T)$ with $|S|, |T| \ge 2$ and no edges between $S$ and $T$. There are fewer than $2^n$ ways to choose the partition, and once have done that, only $2^{\binom{|S|}{2} + \binom{|T|}{2}} \le 2^{\binom{n-2}{2} + 1}$ ways to choose the edges within $S$ and $T$.

This gives us the lower bound $$ d_n \ge 2^{\binom n2} - n 2^{\binom{n-1}{2}} - 2^{n + \binom{n-2}{2}+1} = 2^{\binom n2}\left(1 - \frac{2n+16}{2^n} \right). $$ From here, we can also get a slightly better upper bound \begin{align} d_n &\le 2^{\binom n2} - n d_{n-1} \le 2^{\binom n2} - n2^{\binom {n-1}2}\left(1 - \frac{2(n-1)+16}{2^{n-1}} \right) \\ &\le 2^{\binom n2} \left(1 - \frac{2n}{2^n} + \frac{8n(n+7)}{2^{2n}}\right). \end{align} So we can conclude that $d_n = 2^{\binom n2}\left(1 - \frac{2n}{2^n} + O(\frac1{2^n})\right).$

Related Question