Proving Connectivity Above the Threshold

The Connectivity Claim

For a random graph to be connected, it is not enough that most vertices have neighbors: there must be no separated group of vertices at all. Near the connectivity threshold, isolated vertices are the first obstruction to disappear. Above that threshold, one must also rule out components containing two or more vertices. The proof does this by bounding both kinds of obstruction.

Throughout, \(\log\) is the natural logarithm, and \(G(n,p)\) is the random simple graph with vertex set \(\{1,\dots,n\}\), in which each of the \(\binom n2\) possible edges is included independently with probability \(p\). A graph is connected if every pair of its vertices is joined by a path. We consider a sequence \(\omega=\omega(n)\) with \(\omega(n)\to\infty\), and set

L=\log n+\omega(n),\qquad p=\frac{L}{n}.

Assume \(0\le p\le1\) for all sufficiently large \(n\), so this is a valid edge probability. Since \(L\to\infty\), the estimates below concern sufficiently large \(n\). We will prove that the probability that \(G(n,p)\) is connected tends to \(1\).

Theorem: If \(\omega(n)\to\infty\) and \(p=(\log n+\omega(n))/n\) is a valid probability, then \(G(n,p)\) is connected with probability tending to \(1\) as \(n\to\infty\).

First Obstruction: Isolated Vertices

A vertex is isolated if it has degree zero. For a fixed vertex, isolation requires all \(n-1\) incident edges to be absent. Independence of edge choices therefore gives probability \((1-p)^{n-1}\). Let \(X\) denote the number of isolated vertices. By summing the isolation probabilities over the \(n\) vertices,

\mathbb{E}[X]=n(1-p)^{n-1} \le n\exp\bigl(-p(n-1)\bigr) =\exp\left(-\omega+\frac{L}{n}\right) \le e\,\exp(-\omega).

Here \(1-p\le e^{-p}\), and the last inequality uses \(L/n=p\le1\). Since \(\omega\to\infty\), this expectation tends to zero. The probability that at least one isolated vertex exists is at most \(\mathbb{E}[X]\): indeed, \(X\ge1\) on that event, so its probability is at most the expected value of \(X\). Thus

\Pr(\text{there is an isolated vertex})\longrightarrow 0.

This estimate rules out components of size one. It does not by itself establish connectivity: a disconnected graph can have components of size two or more. We next bound those possibilities.

Worked Example: Bounding Isolated Vertices

Take \(n=16\) and \(\omega=\log 16\). Then \(L=\log16+\log16=2\log16\), so \(p=2\log16/16=\log2/2\). For a fixed vertex, the probability of being isolated is \((1-\log2/2)^{15}\). Summing over the \(16\) vertices and applying \(1-p\le e^{-p}\),

\mathbb{E}[X] =16(1-\log2/2)^{15} \le16\exp(-15\log2/2) =16\cdot2^{-15/2} =2^{-7/2}.

The exponent in the last equality follows from \(16=2^4=2^{8/2}\), so \(2^{8/2}2^{-15/2}=2^{-7/2}\). Therefore the probability of any isolated vertex is at most \(2^{-7/2}\). Check: the bound from the general estimate is \(e\exp(-\omega)=e\exp(-\log16)=e/16\); since \(p=\log2/2\le1\), the preceding general argument also applies. The direct calculation above uses the exact value \(p=\log2/2\) in the isolation estimate.

Disconnected Graphs Have a Witnessing Set

A component is a maximal connected subgraph. If a graph is disconnected and has no isolated vertices, choose a component with the fewest vertices. It has at least two vertices, and it has at most \(n/2\): if it had more than \(n/2\), every other component would together have fewer than \(n/2\) vertices, contradicting its being a smallest component. The chosen component has no edges to its complement.

Lemma: If a graph on \(n\ge2\) vertices is disconnected and has no isolated vertices, then there is a vertex set \(S\) with \(2\le |S|\le n/2\) and no edge between \(S\) and \(V\setminus S\).

Proof. A disconnected graph has at least two components. Choose a component with the fewest vertices and let \(S\) be its vertex set. Since the graph has no isolated vertices, this component contains at least two vertices. Since it is a smallest component among at least two components, its size is at most the size of the union of all the other components; hence \(|S|\le n-|S|\), or \(|S|\le n/2\). By the definition of a component, no edge joins \(S\) to \(V\setminus S\). \(\square\)

For a fixed set \(S\) of size \(k\), there are exactly \(k(n-k)\) possible edges between \(S\) and its complement. In \(G(n,p)\), the probability that all these edges are absent is \((1-p)^{k(n-k)}\), which is at most \(\exp(-pk(n-k))\). There are \(\binom nk\) choices of \(S\). A union bound therefore gives

\Pr(\text{some such set }S) \le \sum_{k=2}^{\lfloor n/2\rfloor} \binom nk\exp\bigl(-pk(n-k)\bigr).

This bound counts some sets that are not components: it does not require any edges inside \(S\), nor does it require that the induced graph on \(S\) be connected. That deliberate overcount is valid for an upper bound. We now show that the sum tends to zero.

Estimating the Component-Size Sum

Use \(\binom nk\le(en/k)^k\), where \(e\) is the base of the natural logarithm. The summand is at most

\left(\frac{en}{k}\exp\left[-L\left(1-\frac{k}{n}\right)\right]\right)^k,

because \(p=L/n\). The useful bound depends on the size of \(k\), so split the sum at \(n/L\).

Small sets: \(2\le k\le n/L\).
Here \(Lk/n\le1\), so \(-Lk(1-k/n)=-Lk+Lk^2/n\le-Lk+k\). The summand is therefore at most \(\left(e^2e^{-\omega}/k\right)^k\), since \(ne^{-L}=e^{-\omega}\). Put \(q=e^2e^{-\omega}\). For sufficiently large \(n\), \(q<1\), and the sum over this range is at most \(\sum_{k=2}^{\infty}q^k=q^2/(1-q)\), which tends to zero.

Larger sets: \(n/L<k\le n/2\).
Now \(1-k/n\ge1/2\), so the exponential factor in the summand is at most \(e^{-Lk/2}\). Also \(n/k<L\), so \((en/k)^k<(eL)^k\). Thus the summand is at most \(r^k\), where \(r=eL e^{-L/2}\). As \(L\to\infty\), \(r\to0\); in particular \(r<1\) for sufficiently large \(n\). The sum over this range is at most \(\sum_{k=1}^{\infty}r^k=r/(1-r)\), which tends to zero.

If either range contains no integer \(k\), its contribution is zero and the same bounds remain valid. Combining the two ranges proves that the probability of any set of size between \(2\) and \(n/2\) with no edges leaving it tends to zero.

Proof of the Theorem. If \(G(n,p)\) is disconnected, then either it has an isolated vertex, or it has no isolated vertices. The first event has probability tending to zero by the expectation bound. In the second case, the lemma supplies a set \(S\) of size between \(2\) and \(n/2\) with no edges from \(S\) to its complement. The union-bound estimate and its two-range calculation show that the probability of this event also tends to zero. The probability of a disconnected graph is at most the sum of these two probabilities, so it tends to zero. Therefore the probability of a connected graph tends to \(1\). \(\square\)

Worked Cut-Event Calculations

Worked Example: A Candidate Two-Vertex Component

Continue with \(n=16\) and \(p=\log2/2\). A specified pair \(S\) has no edges to its complement precisely when all edges across the cut are absent. There are \(2\cdot14=28\) possible crossing edges. Thus the probability of no crossing edge for this fixed pair is \((1-p)^{28}\), at most \(\exp(-28p)\). There are \(\binom{16}{2}=16\cdot15/2=120\) possible pairs, so the probability that any pair has no edge to its complement is at most

120\exp(-28\log2/2) =120\exp(-14\log2) =\frac{120}{2^{14}} =\frac{120}{16384} =\frac{15}{2048}.

Check: this event is necessary for a specified pair to be a component, but not sufficient: the edge joining the two vertices must also be present for the pair to form a connected component. Ignoring that extra requirement can only increase the probability bound, as intended.

Worked Example: A Balanced Cut

Again take \(n=16\) and \(p=\log2/2\), and fix a set \(S\) of size \(8\). Its complement also has size \(8\), so the number of possible crossing edges is \(8\cdot8=64\). The probability that this particular cut has no crossing edge is \((1-p)^{64}\le\exp(-64p)\). There are \(\binom{16}{8}=12870\) choices of \(S\), so the probability that any such balanced set has no crossing edge is at most

12870\exp(-64\log2/2) =12870\exp(-32\log2) =\frac{12870}{2^{32}}.

Check: the factor \(64\) is the number of crossing edges, not the number of edges inside \(S\). The cut probability uses only crossing edges; the number of candidate cuts is counted separately by \(\binom{16}{8}\).

Why the Two Obstructions Matter

The argument has two distinct jobs. The expectation estimate handles components of size one. The cut-set sum handles every possible component size from two through \(n/2\), without assuming in advance that the component is small in any stronger sense. It is the factor \(\exp(-pk(n-k))\)—the cost of forbidding all edges across the cut—that makes the larger-component events unlikely.

Common pitfall: stopping after isolated vertices. The calculation \(\mathbb{E}[X]\to0\) only shows that isolated vertices are unlikely. It does not imply that every remaining vertex lies in one component. For example, a graph could consist of two disjoint edges: it has no isolated vertices, but it is disconnected. In the random-graph proof, the correction is to bound the probability of a no-crossing set for every size \(2\le k\le n/2\), in addition to bounding isolated vertices.

Another tempting but insufficient estimate is to use only \(n-k\ge n/2\) for every \(k\le n/2\). This gives a crossing-edge probability bound with an exponential factor \(e^{-Lk/2}\), which is useful for larger \(k\) but loses too much for the smallest sets. The small-set range instead uses \(k\le n/L\), retaining almost all of the exponent \(-Lk\). The split is what makes both bounds effective.

Check Your Understanding

For each question, identify the event being bounded and the estimate that applies.

Why does the probability of at least one isolated vertex not exceed the expected number of isolated vertices?
Why can a smallest component in a disconnected graph with no isolated vertices be chosen to have size at most \(n/2\)?
For a fixed set \(S\) with \(|S|=k\), how many possible edges cross from \(S\) to its complement?
Why does the union bound for sets with no crossing edges not need to require that \(S\) be internally connected?
In the proof, which estimate uses \(k\le n/L\), and which uses \(k\le n/2\)?