Here’s a proof by induction.
Let $w(n) = \sum\limits_{G\in C_n}(-1)^{e(G)}$, where $e(G)$ is the number of edges in $G$. I will assume that the vertex set of $G\in C_n$ is $[n] = [1,n]\cap\mathbb{Z}^+$. Suppose that $w(k) = (-1)^{k-1}(k-1)!$ for $1\le k \le n$.
Let $H$ be a labeled partition of $[n]$. Suppose that $H$ has components (parts) $H_1,\dots,H_k$. Denote $v_i = |H_i|$. Let $P(H)$ be the set of permutations whose cycles are exactly $H_1,\dots,H_k$ (in any internal order). Clearly $$\vert P(H)\vert = \prod_{i=1}^k(v_i-1)!,$$ and if $G_n$ is the set of all labeled partitions of $[n]$, $$\sum_{H\in G_n}\vert P(H)\vert = n!.$$
Let $C_{n+1}(H)$ be the set of $G\in C_{n+1}$ that decompose into connected components $H$ after deleting vertex $n+1$. Consider a component $H_i$ of $H$. If $G\in C_{n+1}(H)$, vertex $n+1$ must be adjacent in $G$ to at least one vertex of $H_i$. For $j=1,\dots,v_i$ there are $\dbinom{v_i}{j}$ ways to attach vertex $n+1$ to $j$ vertices of $H_i$. It follows that
$$\begin{align*}
\sum_{G\in C_{n+1}(H)}(-1)^{e(G)} &= \prod_{i=1}^k\sum_{j=1}^{v_i}\binom{v_i}{j}(-1)^jw(v_i)\\
&= \prod_{i=1}^k(-1)^{v_i-1}(v_i-1)!\sum_{j=1}^{v_i}\binom{v_i}{j}(-1)^j\\
&= \prod_{i=1}^k(-1)^{v_i-1}(v_i-1)!(-1)\\
&= \prod_{i=1}^k(-1)^{v_i}(v_i-1)!\\
&= (-1)^n\prod_{i=1}^k(v_i-1)!\\
&= (-1)^n\vert P(H)\vert
\end{align*}$$
and hence that
$$\begin{align*}
w(n+1) &= \sum_{H\in G_n}\quad\sum_{G\in C_{n+1}(H)}(-1)^{e(G)}\\
&= \sum_{H\in G_n}(-1)^n \vert P(H)\vert\\
&= (-1)^n\sum_{H\in G_n}\vert P(H)\vert\\
&= (-1)^n n!.
\end{align*}$$
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).$
Best Answer
A further HINT: The hint tells you that
$$e^{B(x)}=\sum_{k\ge 0}\frac{\big(B(x)\big)^k}{k!}\,,$$
so
$$e^{B(x)}-1=\sum_{k\ge 1}\frac{\big(B(x)\big)^k}{k!}\,.$$
A simple graph on $n$ vertices has at least one component, so . . .
You may find Problem $413$ of this web page or Section $4$ of this PDF helpful.