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.

Analytic Combinatorics, the number $K_n$ of labeled connected graphs on $n$ vertices satisfies $K_n=2^{{n\choose 2}}(1-2n2^{-n}+o(2^{-n}))$. $\endgroup$ – Richard Stanley Jun 27 at 17:42