Return to Answer

It turns out that my hypothesis (4) was completely wrong. Besides Example 11.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.

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.

It turns out that my hypothesis (4) was completely wrong. Besides Example 11.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{k}{2^k} \end{equation}

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

It turns out that my hypothesis (4) was completely wrong. Besides Example 11.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.

It turns out that my hypothesis (4) was completely wrong. Besides Example 11.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_{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.

Note: 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.

It turns out that my hypothesis (4) was completely wrong. Besides Example 11.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{k}{2^k} \end{equation}

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