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. 



Asymptotic formula for the number of connected graphs
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*](https://users.cecs.anu.edu.au/~bdm/papers/BCM_Connected1.pdf). 


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.


