Consider a "random" undirected graph, with n nodes and (on average) k edges assigned to each node, such that the edge connects the node to a randomly chosen node in the graph. What is the probability that this graph will be connected, i.e. contain a path from every node to every other node?

  • $\begingroup$ Do you mean, in your construction of a random graph, that an edge between two nodes occurs with probability $k/n$, and that the probability of an edge is independent of the probability of all other edges? $\endgroup$ – Tom Hallward May 11 '18 at 17:50
  • 2
    $\begingroup$ "strongly connected" is a term used for directed graphs, but there is no hint of directed edges in the remainder of the question. $\endgroup$ – vadim123 May 11 '18 at 17:58
  • $\begingroup$ the graph should be undirected, fixed. i just mean to ask what the probability is that every node has some path to every other node. $\endgroup$ – user561046 May 11 '18 at 18:23
  • $\begingroup$ @TomHallward that seems like it would work for the construction, because that should result in nk total edges $\endgroup$ – user561046 May 11 '18 at 18:24
  • $\begingroup$ To @vadim123's point, here is a clarification of the notions of strongly directed and directed. Link $\endgroup$ – Tom Hallward May 11 '18 at 18:32

See wikipedia about the Erdos-Renyi model. Two key properties are:

  1. If $pn<(1-\epsilon)\log n$, then the graph is almost surely disconnected.

  2. If $pn>(1+\epsilon)\log n$, then the graph is almost surely connected.


Let me first introduce some terminology: $G(n,p)$ is a random graph on $n$ vertices in which each edge is put with probability $p$.

A classical result in the theory of random graphs states that if $p = \frac{\log n + c}{n}$ (where $c$ is constant) then the probability that a graph drawn according to $G(n,p)$ is connected tends to $e^{-e^{-c}}$ as $n \to \infty$.

Using this, you can show that if $c(n) \to -\infty$ and $p = \frac{\log n + c(n)}{n}$ then the probability that a graph drawn according to $G(n,p)$ is connected tends to $0$, and if $c(n) \to \infty$ the probability tends to $1$.

You can obtain similar results in the $G(n,m)$ model, in which you put $m$ random edges. In this case instead of $p = \frac{\log n + c}{n}$ you should consider $m = \frac{n}{2} (\log n + c)$.

Finally, if you draw a random $d$-regular graph on $n$ vertices for $d \geq 3$, then the probability that it is connected tends to $1$ as $n \to \infty$. (For $d = 2$, it tends to $0$.)


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.