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

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?

• 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? – Tom Hallward May 11 '18 at 17:50
• "strongly connected" is a term used for directed graphs, but there is no hint of directed edges in the remainder of the question. – vadim123 May 11 '18 at 17:58
• 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. – user561046 May 11 '18 at 18:23
• @TomHallward that seems like it would work for the construction, because that should result in nk total edges – user561046 May 11 '18 at 18:24
• To @vadim123's point, here is a clarification of the notions of strongly directed and directed. Link – 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$.)