Introduction:

Recently, I wondered whether given the set of graphs with distinguishable vertices, , whether most of these graphs might be connected. This set may correspond to the state space of a biological network whose connectivity varies over time such as a brain. The relevance of connectivity here is that it guarantees a path between different fundamental nodes.

Initially, I thought we might need to derive the asymptotic formula for the number of connected graphs with vertices. It turns out that there’s a much simpler approach using the Erdős–Rényi random graph model. I realised this after discussing a related question with mathematicians on the MathOverflow.

Demonstration:

Olivier Fouquet and lambda made very helpful remarks regarding the connection with 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

Using this insight we may proceed 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 vertices the probability that any finite subset of vertices, and , are joined to a common vertex 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 :

\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.

As a corollary we may deduce that for large the number of connected graphs is given by:

\begin{equation} \lvert K_N \rvert \sim 2^{N \choose 2} \end{equation}

Discussion:

I’m quite satisfied with this demonstration using probabilistic arguments as it’s a lot simpler than the approach proposed by [1] and [2]. However, I must say that [1] and [2] contain interesting insights and methods that I haven’t seen before. For this reason both of these publications are on my reading list.

References:

  1. E. Bender, E. Canfield & B. McKay. The Asymptotic Number of labeled Connected Graphs with a Given Number of I/ertices and Edges. 1990.
  2. Example II.15 in Flajolet and Sedgewick, Analytic Combinatorics. 2009.