Asymptotic number of connected simple graphs of $n$ labelled vertices 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?

 A: 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).$
