Asymptotic formula for the number of connected graphs

Question

It can be shown that the set of graphs with $N$ vertices $G_N$ has cardinality:

\begin{equation} \lvert G_N \rvert = 2^{N \choose 2} \tag{1} \end{equation}

Recently, I wondered how much bigger $\lvert G_N \rvert$ is compared to the number of graphs with $N$ vertices that are path-connected, $PC_N$.

If we denote the set of Hamiltonian paths by $H_N$ we can easily show that:

\begin{equation} H_N \subset PC_N \tag{2} \end{equation}

and by Stirling's approximation:

\begin{equation} \lvert H_N \rvert = N! \sim \sqrt{2\pi N} \big(\frac{N}{e}\big)^N \tag{3} \end{equation}

and therefore $\lvert PC_N \rvert$ must grow exponentially fast.

Now, I'm curious about asymptotic formulas for $\lvert PC_N \rvert$ and I'm fairly confident that for large $N$:

\begin{equation} \frac{\lvert PC_N \rvert}{\lvert G_N \rvert} \leq e^{-N} \tag{4} \end{equation}

but I suspect that a proof for this statement would be fairly subtle.

Note: I didn't make use of a computer before formulating this hypothesis but in retrospect I should have analysed the connectivity of random graphs, as suggested by Olivier Fouquet. This would have given me more insight into the problem.

Answer 1

It turns out that my hypothesis (4) was completely wrong. Besides Example II.15 in Flajolet and Sedgewick, Analytic Combinatorics pointed out by Richard Stanley, another useful reference is The Asymptotic Number of labeled Connected Graphs with a Given Number of Vertices and Edges.

Their demonstration is fairly technical and the main finding is that if $c(N,q)$ describes the number of connected labeled graphs with $N$ vertices and $q \leq {N \choose 2}$ edges we have:

\begin{equation} c(N,q) \sim {{N \choose 2} \choose q}e^{-Ne^{-\frac{2q}{N}}} \end{equation}

and since $\lim\limits_{n \to \infty} \frac{5N}{{N \choose 2}}=0$ for large $N$, due to the symmetry of binomial coefficients, we have:

\begin{equation} \sum_{q=5N}^{{N \choose 2}}c(N,q) \sim \sum_{q=5N}^{{N \choose 2}} {{N \choose 2} \choose q} \sim 2^{{N \choose 2}} \end{equation}

so for large $N$ almost all labeled graphs are connected.

Remark: Although I say that the paper is technical, I don't mean this in a bad way. It's full of interesting insights and contains clever methods that I haven't seen before.

Addendum:

Olivier Fouquet and lambda made very helpful remarks regarding random graphs. In particular, I would like to point out lambda's remark that:

...the Erdős–Rényi random graph model with edge probability 1/2 gives the uniform distribution on labelled graphs

It follows that Olivier Fouquet is right that there exists a much simpler proof that almost all simple graphs are connected. The proof is as follows:

Let's first note that the Erdős–Rényi random graph model with edge probability 1/2 gives the uniform distribution on labelled graphs since for each pair of vertices they are either joined by an edge or not. It follows that given a graph with $N$ vertices the probability that any finite subset of $k$ vertices, $V \subset \{v_i\}_{i=1}^N$ and $\lvert V \rvert=k$, are joined to a common vertex $v_l \notin V$ is given by:

\begin{equation} 1 - {N \choose k}\big(1-\frac{1}{2^k} \big)^{N-k} \end{equation}

Now, we would like to show that:

\begin{equation} \lim\limits_{N \to \infty}{N \choose k}\big(1-\frac{1}{2^k} \big)^{N-k}=0 \end{equation}

Let's first note that:

\begin{equation} {N \choose k}=\frac{N!}{k!(N-k)!} \leq N^k \end{equation}

\begin{equation} \big(1-\frac{1}{2^k} \big)^{N-k} \propto \big(1-\frac{1}{2^k} \big)^N \sim e^{-\frac{N}{2^k}} \end{equation}

and taking logarithms we find that for fixed $k \in \mathbb{N}$:

\begin{equation} \lim_{N \to \infty} \frac{\ln N}{N} < \frac{1}{k2^k} \end{equation}

so we may conclude that a simple graph is connected with probability 1.