What is the probability that a graph containing n nodes with k random edges each will be strongly connected?

Question

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?

Answer 1

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.

Answer 2

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$.)