Connectivity in the Binomial Random Graph
A graph can have many edges and still fail to be connected: a small set of vertices may remain separated from the rest. In the binomial random graph, the edge probability at which connectivity becomes likely is not a constant. It decreases with the number of vertices, and its leading scale is \((\log n)/n\). Understanding this scale requires distinguishing a broad threshold transition from the narrower critical window, where the probability of connectivity has a nontrivial limit.
Throughout, \(\log\) denotes the natural logarithm. A sequence of events holds with high probability if its probability tends to \(1\) as \(n\to\infty\). The expected degree of a fixed vertex in \(G(n,p)\) is \((n-1)p\), because each of its \(n-1\) possible incident edges is present with probability \(p\).
The Threshold Scale and the Critical Window
The connectivity threshold is the scale at which the probability of being connected changes from tending to \(0\) to tending to \(1\). Its leading scale is \((\log n)/n\). At that scale the expected degree is approximately \(\log n\), since \((n-1)(\log n)/n=(1-1/n)\log n\). The logarithmic factor matters: a fixed expected degree is not the connectivity scale.
The first two cases describe the threshold on either side: the offset from \(\log n\) diverges, even though it is smaller in magnitude than \(\log n\). The fixed-\(c\) case is the critical window. Its width in \(p\) is of order \(1/n\), since changing \(c\) by a fixed amount changes \(p_n\) by that amount divided by \(n\). For every fixed \(c\), the formula gives a limit strictly between \(0\) and \(1\). Increasing \(c\) makes the limit larger.
This asymptotic theorem is stated here as a standard result; a full proof requires both the distribution of isolated vertices at this scale and estimates ruling out other disconnected components. Those ingredients are developed in the material on isolated vertices and connectivity bounds. The examples below use the theorem to interpret the scale, rather than treating the limiting formula as an exact finite-\(n\) probability.
Two Basic Checks on Connectivity
Proof. An isolated vertex has degree zero, so no path from it can reach any other vertex. When \(n\ge2\), there is at least one other vertex; therefore a graph with an isolated vertex is not connected. Thus the event that the graph is connected is contained in the event that it has no isolated vertices, and taking probabilities gives the inequality. \(\square\)
Proof. Assign an independent random number \(U_e\), uniformly distributed on \([0,1]\), to each possible edge \(e\). For a parameter \(p\), include \(e\) exactly when \(U_e\le p\). For each fixed \(p\), the edge decisions are independent and each has probability \(p\), so this construction has distribution \(G(n,p)\). If \(p\le q\), every edge included at parameter \(p\) is also included at parameter \(q\). Adding edges cannot destroy any path that already existed. Hence the event of connectivity at \(p\) is contained in the event of connectivity at \(q\), and its probability is no larger. \(\square\)
These facts help interpret the threshold result. Isolated vertices are an immediate obstruction, and increasing \(p\) cannot reduce the chance of connectivity. Neither fact alone gives the critical-window limit: one must also analyze how likely other disconnected components are.
Worked Example: The Exact Probability for Three Vertices
Let \(G(3,p)\) have vertices \(\{1,2,3\}\) and possible edges \(12,13,23\). Find its exact probability of being connected.
A graph on these three vertices is connected exactly when it has at least two of the three possible edges. There are three choices for the single missing edge when exactly two are present. Independence gives probability \(p^2(1-p)\) for each such choice, and probability \(p^3\) when all three are present. Therefore $$ \Pr(G(3,p)\text{ is connected})=3p^2(1-p)+p^3=3p^2-2p^3. $$
At \(p=0.4\), the probability is \(3(0.4)^2(1-0.4)+(0.4)^3=3(0.16)(0.6)+0.064=0.288+0.064=0.352\). As a check, the three mutually exclusive cases with exactly two edges contribute \(0.288\), and the case with all three contributes \(0.064\), again totalling \(0.352\). This exact finite-graph calculation is not the critical-window limit, which concerns \(n\to\infty\).
Worked Example: Reading the Window at \(c=0\)
At the centre of the critical window, take \(p_n=(\log n)/n\). The window theorem applies with fixed \(c=0\), so the limiting connectivity probability is \(\exp(-e^0)=\exp(-1)\), approximately \(0.3679\). The value is strictly between \(0\) and \(1\), consistent with this being a window rather than a regime where connectivity already has probability tending to \(0\) or \(1\).
For a scale check at \(n=1000\), \(\log(1000)\approx6.9078\), so \(p_{1000}\approx6.9078/1000=0.0069078\). The expected degree is \((1000-1)p_{1000}\approx999(0.0069078)=6.9009\), close to \(\log(1000)\). The limit \(\exp(-1)\) is an asymptotic prediction; it is not asserted to equal the exact connectivity probability at \(n=1000\).
Check: the parameter satisfies \(1000p_{1000}=\log(1000)\), as required for \(c=0\), and the limiting value comes from substituting \(c=0\) into \(\exp(-e^{-c})\).
Worked Example: Comparing Fixed Offsets
Compare the limiting connectivity probabilities for the fixed offsets \(c=-2,0,2\). The theorem gives \(\exp(-e^{-c})\) in each case.
For \(c=-2\), the limit is \(\exp(-e^2)\). Since \(e^2\approx7.3891\), this is approximately \(\exp(-7.3891)\approx0.00062\). For \(c=0\), it is \(\exp(-e^0)=\exp(-1)\approx0.3679\). For \(c=2\), it is \(\exp(-e^{-2})\); since \(e^{-2}\approx0.1353\), this is approximately \(\exp(-0.1353)\approx0.8734\).
Thus the same window formula predicts limits of about \(0.00062\), \(0.3679\), and \(0.8734\), respectively. The order is consistent with monotonicity: the corresponding edge probabilities increase as \(c\) increases. Each comparison concerns a sequence of graphs with \(n\to\infty\), not one finite graph.
Check: substituting the offsets into \(p_n=(\log n+c)/n\) gives \(np_n-\log n=c\) in each case; the three limits above are obtained by using those same values of \(c\) in \(\exp(-e^{-c})\).
Common Pitfall: Confusing Mean Degree with Connectivity
A tempting but incorrect threshold estimate is \(p=1/n\), based on the condition \(np\approx1\). That condition describes a constant-order expected degree, but the connectivity threshold is at \(p\approx(\log n)/n\). At the latter scale, the expected degree is approximately \(\log n\), not \(1\). The distinction is important: having a moderate expected degree does not by itself ensure that every vertex can reach every other vertex.
A second pitfall is to read \(\exp(-e^{-c})\) as an exact probability for a fixed \(n\). It is a limit as \(n\to\infty\) with \(c\) held fixed. For finite \(n\), the exact connectivity probability is generally different; the three-vertex calculation above illustrates how an exact probability is computed in a small case.
Finally, the critical-window statement is not the same as either side of the threshold. Fixed \(c\) gives a nontrivial limiting probability. The regimes \(c_n\to-\infty\) and \(c_n\to+\infty\), under the stated size condition, give limits \(0\) and \(1\), respectively. Keeping those quantifiers separate prevents a common misreading of the threshold.
Check Your Understanding
Use the definitions and threshold statement to answer the following questions.
- In \(G(n,p)\), why is the expected degree of a fixed vertex \((n-1)p\), rather than \(np\)?
- For fixed \(c=1\), write the critical-window edge probability and the limiting connectivity probability.
- Explain why an isolated vertex rules out connectivity when \(n\ge2\).
- What distinction does the condition \(c_n=o(\log n)\) make in the two threshold regimes?
- Why is the critical-window limit not an exact formula for the connectivity probability of a finite graph?