3
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ According to Example 11.15 in Flajolet and Sedgewick, 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
  • 2
    $\begingroup$ Number of connected labeled graphs with n nodes is tabulated, with many links and references, at oeis.org/A001187 $\endgroup$ – Gerry Myerson Jun 30 at 5:37
  • 2
    $\begingroup$ It's Example II.15, not 11.15 $\endgroup$ – Slava Rychkov Jul 3 at 16:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "So for large $N$ almost all labeled graphs are connected" Surely that conclusion can be obtained in a much simpler way than with the full asymptotic. $\endgroup$ – Olivier Jun 30 at 2:01
  • $\begingroup$ @Olivier I'm curious about your statement as I have a growing interest in graph theory but I'm not a graph theorist. Might you know of an elementary demonstration? $\endgroup$ – Aidan Rocke Jun 30 at 4:31
  • 1
    $\begingroup$ I'm not a graph theorist either, but the statement seemed intuitive to me (it is quite hard for a large random graph not too be connected). Anyway, the article The $k$‐Connectedness of Unlabelled Graph by Walsh and Wright contains a much stronger statement. $\endgroup$ – Olivier Jun 30 at 10:20
  • 2
    $\begingroup$ Combinatorics and overcounting is another way. There are N choose k ways to divide the vertex set into a disconnected set of size k and one of size N-k, and the number of labeled graphs on the pair that are disconnected has 2 to a significantly smaller exponent than N choose 2, giving that disconnected graphs are fewer in number by a factor of about (2^(N-1))/N. Gerhard "Simple Arguments Really Do Count" Paseman, 2019.07.01. $\endgroup$ – Gerhard Paseman Jul 1 at 15:41
  • 1
    $\begingroup$ Incidentally, the proof is wrong. The probability of a particular $k$-set being disconnected from the rest is $2^{-k(N-k)}$. Multiply by $\binom Nk$ for the number of $k$-sets, then sum over $k=1\ldots N-1$ (or $k=1\ldots N/2$ if you like). You will see that the term for $k=1$ is easily the largest. $\endgroup$ – Brendan McKay Jul 1 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.