The Giant Component Above Mean Degree One

From Mean Degree to a Giant Component

In a sparse random graph, each possible edge is present with a probability that tends to zero as the graph grows, while the expected degree remains bounded. When that expected degree is greater than one, a component exploration can continue for a positive proportion of the vertices. The resulting large component is called a giant component. Its limiting size is not the same as the probability that a uniformly chosen vertex belongs to a component of any particular fixed size.

Throughout, \(c>1\) is fixed, \(n\) tends to infinity, and \(n>c\). The random graph \(G(n,c/n)\) has vertex set \(\{1,\ldots,n\}\); each of the \(\binom n2\) possible edges is included independently with probability \(p=c/n\). A component is a maximal connected subgraph. Write \(C_1\) for a largest component, and \(C_2\) for a second-largest component, choosing either arbitrarily in case of ties. A component is called giant when its size is proportional to \(n\), rather than bounded as \(n\) grows.

Exploring the component of a vertex reveals, for each newly reached vertex, a number of new neighbors that is approximately Poisson with mean \(c\). The corresponding branching-process approximation has independent offspring counts with distribution \(\operatorname{Poisson}(c)\). The earlier material on component exploration and branching processes establishes this local approximation for any fixed number of exploration steps. It predicts the chance that a vertex’s component exploration dies out, and hence the proportion of vertices in finite components.

The Branching-Process Equation

For this process, \(q\) is the smallest solution in \([0,1]\) of a simple equation. To see why, let \(q_t\) be the probability that extinction has occurred by generation \(t\), with generation zero consisting of the initial individual. Then \(q_0=0\). If the initial individual has \(j\) children, extinction by generation \(t+1\) occurs exactly when each of those \(j\) child processes is extinct by generation \(t\). Thus, using the Poisson probabilities,

The events “extinction by generation \(t\)” increase with \(t\), so \(q_t\) increases to \(q\). Taking limits in the recursion gives \(q=e^{-c(1-q)}\). Moreover, \(q\) is the smallest solution in \([0,1]\): the function \(x\mapsto e^{-c(1-x)}\) is increasing, and iteration from \(q_0=0\) stays below any fixed point in that interval. Since every individual has finitely many children, extinction is equivalent to the entire family tree having finitely many individuals. A process that never becomes extinct has at least one individual in every generation, and therefore has infinitely many individuals.

Proof. Put \(f(x)=1-e^{-cx}-x\) for \(x\in[0,1]\). Then \(f(0)=0\), \(f'(x)=ce^{-cx}-1\), and \(f''(x)=-c^2e^{-cx}<0\). Since \(c>1\), \(f'(0)=c-1>0\), so \(f(x)>0\) for all sufficiently small positive \(x\). Also \(f(1)=-e^{-c}<0\). Continuity gives at least one root in \((0,1)\). The derivative \(f'\) is strictly decreasing because \(f''<0\). It starts positive and can change sign at most once; after it becomes negative, \(f\) is strictly decreasing. Consequently \(f\), which first increases from zero and then decreases, can cross zero at most once after \(x=0\). This proves uniqueness of the positive root. Substituting \(q=1-\rho\) into \(q=e^{-c(1-q)}\) gives \(1-\rho=e^{-c\rho}\), exactly the displayed equation. The smaller fixed point \(q<1\) is the extinction probability, while \(1\) is the other fixed point. \(\square\)

The positive solution is the predicted fraction of vertices whose exploration does not die out. This prediction is made precise by the standard giant-component theorem for \(G(n,c/n)\): for each fixed \(c>1\), with probability tending to one as \(n\to\infty\), \(|C_1|/n\) tends to \(\rho\), and \(|C_2|/n\) tends to zero. This theorem is a standard result; its full proof, which requires controlling explorations beyond a fixed number of steps, is beyond this tutorial. The equation and its positive solution have been derived here, and the following fixed-size calculations explain how the branching process describes the finite components.

Components of a Fixed Size

For each fixed integer \(k\ge1\), the branching-process approximation gives the limiting probability that a uniformly chosen vertex lies in a component of size \(k\). Denote this probability by \(q_k\). The exploration must produce a finite tree of \(k\) vertices. The standard enumeration of rooted labelled trees gives

This is a fixed-\(k\) statement: \(k\) is held constant while \(n\) grows. Equivalently, the proportion of all vertices that lie in components of size exactly \(k\) converges in probability to \(q_k\). This fixed-size limit is part of the standard exploration approximation. The tree formula can also be checked by counting components directly: choose their \(k\) vertices, choose a labelled tree on them, require its \(k-1\) edges, and forbid all other edges that would connect the chosen vertices to the rest of the graph or add an internal edge. For fixed \(k\), connected components with cycles have vanishing vertex proportion, because a connected graph on \(k\) vertices containing a cycle has at least \(k\) edges; its expected number of occurrences as a component is bounded as \(n\) grows, while it accounts for only \(k\) vertices per occurrence.

The sequence \((q_k)\) accounts for the extinction probability: \(\sum_{k\ge1}q_k=q\). One way to see the identity is through the standard rooted-tree generating function. Cayley’s formula gives \(k^{k-1}\) rooted labelled trees on \(k\) labels, and their exponential generating function \(T(z)=\sum_{k\ge1}k^{k-1}z^k/k!\) satisfies \(T=ze^T\). For \(c>1\), the sum of the displayed \(q_k\) is \(T(ce^{-c})/c\); this is the smaller solution of \(q=e^{-c(1-q)}\), hence equals the extinction probability. Cayley’s formula and the generating-function identity are standard enumeration results; their proofs are not needed for the component equation derived above.

What “Finite Components” Means Here

For each fixed \(k\), \(q_k\) describes the limiting fraction of vertices in components of exactly \(k\) vertices. Summing over all fixed sizes gives the extinction probability \(q\), and the giant-component theorem says the largest component accounts for the complementary fraction \(\rho=1-q\). The distinction matters: “finite component” in the branching-process calculation means a component with a finite total number of vertices in the limiting branching process. At each finite \(n\), of course, every graph component is finite.

Nor does the fixed-\(k\) formula assert that every component outside \(C_1\) has bounded size uniformly in \(n\). The theorem stated above says the second-largest component is \(o(n)\); that permits components that grow with \(n\) while remaining a vanishing fraction of the whole graph. The fixed-size limits describe components with \(k\) held fixed, not every possible scale below \(n\).

Common Pitfall: Losing a Finite-\(n\) Factor

When counting two-vertex components, the expected fraction is \((2/n)\binom n2p(1-p)^{2(n-2)}\). If \(p=2/n\), the coefficient simplifies to \((2/n)\binom n2(2/n)=2(n-1)/n\), not \(2\). For example, at \(n=10\) it is \(2(9)/10=1.8\), not \(2\). The factor tends to \(2\) as \(n\to\infty\), so dropping it preserves the limit but gives a false exact finite-\(n\) formula. Always simplify finite-\(n\) coefficients before taking a limit.