Chapter 23: Random Graphs and Random Combinatorial Structures

When does a random graph suddenly acquire a giant component?

Start with isolated vertices and add edges at random. At first, each edge joins tiny components. Later, one component can absorb a positive fraction of all vertices, even though the graph still has many isolated vertices. What controls this change, and how is it different from becoming connected?

Write $L_1$ for the number of vertices in the largest component. In an asymptotic family of random graphs, a giant component has order proportional to $n$: its size divided by $n$ stays bounded away from zero with high probability. Every finite graph has a largest component, but that alone does not justify calling it a giant. A graph is connected only when all its vertices lie in one component.

We use elementary probability from Chapter 22: independent choices, binomial variables, expectation, and first- and second-moment bounds. More advanced limiting distributions and branching processes are introduced as needed. The aim is to connect a precise probability model with a proof mechanism and a finite experiment, keeping their conclusions distinct.

23.1 Erdős–Rényi models G(n,p) and G(n,m)

Fix the labeled vertex set $[n]$ and let $N=\binom n2$ be the number of possible unordered pairs. All graphs here are undirected and simple: no loops or parallel edges unless explicitly introduced by the configuration model.

In $G(n,p)$, each of the $N$ pairs is present independently with probability $p\in[0,1]$. For a specified graph $H$ with $h$ edges,

$$ \Pr(G(n,p)=H)=p^h(1-p)^{N-h}. $$

Its edge count is $M\sim\operatorname{Bin}(N,p)$, with mean $Np$ and variance $Np(1-p)$. A fixed vertex has degree $\operatorname{Bin}(n-1,p)$ and expected degree $(n-1)p$. Vertex degrees are not mutually independent: two vertices share their potential connecting edge.

In $G(n,m)$, with integer $0\le m\le N$, choose uniformly among the $\binom Nm$ graphs having exactly $m$ edges. The marginal probability of a given edge is $m/N$, but different edge indicators are generally dependent. For two specified distinct edges,

$$ \Pr(\text{both present})=\frac{m(m-1)}{N(N-1)} $$

when $N\ge2$. Sampling edges without replacement is the relevant mechanism.

Solved comparison. On four vertices there are six possible edges. In $G(4,1/2)$, all 64 graphs have probability $1/64$ and the expected edge count is 3. In $G(4,3)$, exactly 20 graphs are eligible, each with probability $1/20$. Both give a fixed edge marginal probability $1/2$, but a specified pair of edges has probability $1/4$ in the first model and $1/5$ in the second. Matching the expected size does not make the distributions identical.

For $0\lt p\lt1$, conditioning $G(n,p)$ on $M=m$ gives exactly $G(n,m)$, because every graph with $m$ edges has the same unconditioned probability. This identity allows transfers when the edge-count fluctuation and the property under study are controlled; it is not permission to replace every fixed-size model by an independent one.

A useful coupling. Assign independent $U_e\sim\operatorname{Uniform}[0,1]$ to all pairs, and include $e$ at parameter $p$ exactly when $U_e\le p$. Each snapshot has law $G(n,p)$, while snapshots are nested as $p$ increases. Alternatively, a uniform random ordering of all pairs has its first $m$ edges distributed as $G(n,m)$.

Exercise. Find the expected degree in $G(10,12)$. Hint: double-count edge endpoints. Solution: symmetry and $\sum_v d(v)=24$ give $\mathbb E d(v)=24/10=12/5$.

23.2 Threshold phenomena

A graph property is increasing if adding edges cannot destroy it. Having an edge, having a triangle, and being connected are increasing; being a tree is not. A positive function $p_0(n)$ is a threshold function for an increasing property if its probability tends to 0 whenever $p/p_0\to0$, and tends to 1 whenever $p/p_0\to\infty$, within the valid range of $p$. Threshold functions are determined only up to their asymptotic scale.

We say an event holds with high probability, abbreviated w.h.p., if its probability tends to 1 as $n\to\infty$. This does not mean probability 1 at a finite $n$. A sharp threshold has a narrower transition: for every fixed $\varepsilon\in(0,1)$, probabilities at $(1-\varepsilon)p_0$ and $(1+\varepsilon)p_0$ tend to 0 and 1. Not every coarse threshold is sharp in this relative sense.

Solved example: the first edge. The probability of no edge is $(1-p)^N$. If $n^2p\to0$, Markov gives $\Pr(M\ge1)\le Np\to0$. If $n^2p\to\infty$, then

$$ \Pr(M=0)=(1-p)^N\le e^{-Np}\to0. $$

Thus $n^{-2}$ is a threshold scale. At $p=c/n^2$, for fixed $c\gt0$, the probability of at least one edge tends to $1-e^{-c/2}$, rather than to 0 or 1. Constant-factor changes remain within a nontrivial transition, so this example is not sharp in the relative sense above.

The first moment typically proves absence below a proposed threshold. Proving presence above it requires further control: a large expected count alone may be caused by rare outcomes carrying many copies. The second moment handles this for triangles.

Exercise. At $p=2/n^2$, what is the limiting probability of an edge? Hint: the limiting expected edge count is 1. Solution: $1-e^{-1}$, about $0.6321$.

23.3 Connectivity and giant components

Let $L_1\ge L_2$ be the two largest component sizes, taking $L_2=0$ for a connected graph. For fixed $c\gt0$ in $G(n,c/n)$, the classical phase transition states:

• If $c\lt1$, $L_1=O(\log n)$ w.h.p.
• If $c\gt1$, $L_1/n$ converges in probability to $\rho(c)\gt0$, while $L_2=O(\log n)$ w.h.p.

The giant fraction is determined by

$$ \rho=1-e^{-c\rho}, $$

using its unique positive solution for $c\gt1$ and $\rho=0$ for $c\le1$. Convergence in probability means that every fixed error tolerance is exceeded with probability tending to zero. At the critical value, logarithmic and linear descriptions both fail; the largest components occur on the $n^{2/3}$ scale. The critical-window theory is beyond the fixed-$c$ statements used here; a primary treatment is Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent.

Mechanism, with the global proof omitted. Breadth-first exploration reveals edges from a current vertex to unseen vertices. Initially the number of new neighbors is approximately Poisson with mean $c$, suggesting a branching process. Below mean 1 it dies out quickly; above mean 1 it survives with positive probability. Turning this into a giant theorem requires controlling collisions, depletion of unseen vertices, concentration, and uniqueness. Local branching intuition alone does not prove those global conclusions. Section 23.6 derives the survival equation. For a primary exploration proof above the transition, see Bollobás and Riordan, Asymptotic normality of the size of the giant component via a random walk.

Connectivity has a later threshold. For fixed $\varepsilon\in(0,1)$, $G(n,p)$ is disconnected w.h.p. at $p=(1-\varepsilon)\log n/n$, and connected w.h.p. at $p=(1+\varepsilon)\log n/n$. The expected number $I$ of isolated vertices is exactly

$$ \mu_I=n(1-p)^{n-1}. $$

Below this threshold, $\mu_I=n^{\varepsilon+o(1)}\to\infty$. Two specified vertices are both isolated with probability $(1-p)^{2n-3}$, so

$$ \frac{\operatorname{Var}(I)}{\mu_I^2} \le\frac1{\mu_I}+\frac p{1-p}\to0. $$

Chebyshev gives an isolated vertex w.h.p., proving disconnection. Above the threshold, eliminating isolated vertices is necessary but not by itself sufficient: two disjoint triangles have none and are disconnected.

Proof of connectivity above the threshold. Every disconnected graph has a component vertex set of size $1\le k\le n/2$ with no edge crossing to its complement. Therefore

$$ \Pr(\text{disconnected})\le \sum_{k=1}^{\lfloor n/2\rfloor}\binom nk(1-p)^{k(n-k)}. $$

Set $a=\varepsilon/[2(1+\varepsilon)]$. For $k\le an$, use $\binom nk\le(en/k)^k$ and $p(n-k)\ge(1+\varepsilon/2)\log n$, bounding each term by $(e n^{-\varepsilon/2}/k)^k$. Their sum tends to zero. For $an\lt k\le n/2$, the cut has at least $an^2/2$ potential edges. The sum of all binomial coefficients is at most $2^n$, so this part is at most $2^n\exp(-pa n^2/2)\to0$. This proves the sharp connectivity threshold.

Solved distinction. At $c=2$, the giant fraction is about $0.7968$, but the expected isolated-vertex count is asymptotic to $ne^{-2}$, which grows linearly. A giant can therefore coexist with many vertices outside it. The original development of these phenomena appears in Erdős and Rényi, On the evolution of random graphs.

The following exact eight-vertex snapshots continue the opening trace. Teal edges were already present at $p=0.18$; orange edges 23 and 45 merge components by $p=0.26$. Every vertex remains explicitly labeled. The larger component at the right has size six, but the graph still has two components; this finite illustration makes no asymptotic giant claim.

Exercise. Does having no isolated vertex prove connectivity? Hint: use the left diagram. Solution: no. Its four disjoint edges give every vertex degree one, but leave four components.

23.4 Poisson approximation and small subgraph counts

A Poisson variable with parameter $\lambda\ge0$ has probabilities $\Pr(Y=k)=e^{-\lambda}\lambda^k/k!$ for nonnegative integers $k$, with the usual point mass at zero when $\lambda=0$. Its mean and variance both equal $\lambda$. It models counts formed from many individually rare opportunities, but rarity alone does not justify a Poisson approximation when events strongly cluster.

Degree limit. In $G(n,c/n)$, a fixed degree is $\operatorname{Bin}(n-1,c/n)$. For each fixed $k$,

$$ \binom{n-1}{k}\left(\frac cn\right)^k \left(1-\frac cn\right)^{n-1-k} \longrightarrow e^{-c}\frac{c^k}{k!}. $$

This calculation proves convergence in distribution to $\operatorname{Poisson}(c)$. It does not make all vertex degrees independent.

Triangle limit. If $p=c/n$ with fixed $c\gt0$, the triangle count converges in distribution to $\operatorname{Poisson}(c^3/6)$. Its mean tends to $c^3/6$, so the limiting probability of at least one triangle is

$$ 1-e^{-c^3/6}. $$

Proof mechanism via factorial moments. Define $(X)_j=X(X-1)\cdots(X-j+1)$. Its expectation counts ordered lists of $j$ distinct triangles. Vertex-disjoint triangles contribute asymptotically $(c^3/6)^j$. For fixed $j$, overlapping configurations have fewer free vertices relative to their required edges and contribute a quantity tending to zero. The factorial-moment criterion then identifies the Poisson distribution. The criterion is a standard probability theorem; checking the overlap contribution is the combinatorial work. An expectation limit by itself would not prove this distributional limit.

Solved comparison. At $c=1$, the limiting triangle mean is $1/6$ and the limiting triangle-presence probability is $1-e^{-1/6}\approx0.1535$. Thus being at the triangle threshold scale does not mean a triangle occurs with probability tending to 1.

At the connectivity window $p=(\log n+t)/n$, fixed $t\in\mathbb R$, the isolated-vertex count instead converges to $\operatorname{Poisson}(e^{-t})$. Its fixed factorial moments have the exact form

$$ \mathbb E[(I)_j]=(n)_j(1-p)^{j(n-j)+\binom j2}\longrightarrow e^{-jt}. $$

The exponent counts all edges incident to a specified set of $j$ isolated vertices: edges to its complement and its internal pairs. Together with a separate bound excluding nontrivial disconnected components in this window, this gives the classical limit

$$ \Pr(G(n,p)\text{ connected})\longrightarrow e^{-e^{-t}}. $$

The isolated-vertex Poisson limit alone supplies the no-isolated-vertex probability, not connectivity; the extra component bound matters.

Exercise. For $G(n,2/n)$, compute the limiting expected number of triangles and the limiting probability of none. Hint: use $c^3/6$. Solution: the mean is $4/3$ and the probability is $e^{-4/3}$.

23.5 Random regular graphs and configuration models

A $d$-regular graph gives every vertex degree $d$. A uniform random simple $d$-regular graph chooses uniformly among all such graphs on $[n]$, assuming they exist: $nd$ must be even and $0\le d\le n-1$. Its degrees are fixed, unlike the binomial degrees in $G(n,p)$.

The configuration model gives vertex $v$ exactly $d_v$ distinguishable half-edges and uniformly pairs the $L=\sum_v d_v$ half-edges, with $L$ even. Each pair creates an edge between the owning vertices. A pair from one vertex creates a loop; different pairs can create parallel edges. There are $(L-1)!!$ pairings, obtained by choosing the partner of the first half-edge and repeating. Every pairing preserves the degree sequence, counting a loop twice in the degree.

Conditioning this multigraph on being simple gives the uniform simple graph with that degree sequence. Indeed, every such simple graph arises from exactly $\prod_v d_v!$ pairings: assign each vertex's labeled half-edges to its distinct incident edges. This common multiplicity proves uniformity. Deleting loops or collapsing parallel edges instead changes degrees and generally does not produce the same distribution.

Solved exact model. Use three vertices $a,b,c$, each with two labeled half-edges. There are $5!!=15$ pairings.

The probabilities sum to 1, and the probability of simplicity is $8/15$. Conditioned on simplicity, the triangle is the only possible graph. An example pairing is $a_1b_1$, $a_2c_1$, $b_2c_2$.

For fixed $d\ge1$ as $n\to\infty$ through admissible values, the probability of simplicity tends to $\exp(-(d^2-1)/4)$, which is positive. This asymptotic result does not replace the finite $8/15$ calculation. Conditions for broader degree sequences are developed in Janson, The probability that a random multigraph is simple.

Exercise. List the configuration outcomes for four vertices of degree one. Hint: each vertex has one half-edge. Solution: the three perfect matchings are 12,34, 13,24, and 14,23, all simple and equally likely.

23.6 Random trees and branching-process connections

A uniform labeled tree on $[n]$ chooses each of its $n^{n-2}$ trees with the same probability, for $n\ge2$. Prüfer's bijection identifies these trees with words of length $n-2$ over $[n]$. Sampling the letters independently and uniformly, then decoding, therefore samples the tree uniformly.

Solved tree. On $[4]$, the Prüfer word 22 decodes to edges 12,23,24: remove the smallest available leaf 1, then leaf 3, and finally join the two remaining vertices 2 and 4. This star has probability $1/16$. There are four possible stars among the 16 trees, so the probability of obtaining any star is $1/4$.

The degree of vertex $v$ is one plus its number of occurrences in the word. Consequently

$$ d(v)\ \overset{d}=\ 1+\operatorname{Bin}(n-2,1/n),\qquad \mathbb E d(v)=2-\frac2n. $$

For a uniform root, this degree tends to $1+\operatorname{Poisson}(1)$, not $\operatorname{Poisson}(1)$. A uniform large tree and an unconditioned branching tree are different random objects.

A Galton–Watson process begins with $Z_0=1$ individual; each individual independently produces a number $\xi$ of offspring with a specified distribution. For mean offspring $c$, $\mathbb E Z_t=c^t$. With $\xi\sim\operatorname{Poisson}(c)$, its generating function is $f(s)=e^{c(s-1)}$.

Let $q_t$ be the probability the process has died out by generation $t$. Independence of the descendant families gives $q_0=0$ and $q_{t+1}=f(q_t)$. Therefore the eventual extinction probability is the smallest solution in $[0,1]$ of

$$ q=e^{c(q-1)}. $$

It equals 1 for $c\le1$ and is less than 1 for $c\gt1$, as follows from the convex graph of $f(s)$ and its slope $f'(1)=c$. The survival probability $1-q$ satisfies the giant-component equation in Section 23.3. For $c\lt1$, the expected total progeny is $\sum_{t\ge0}c^t=1/(1-c)$. At $c=1$, extinction still occurs with probability 1, while this expected total is infinite.

Early exploration of $G(n,c/n)$ resembles this process because few discovered vertices mean few collisions and most potential neighbors remain unseen. It is an approximation over limited exploration, not a statement that a finite graph component is literally an independent offspring tree.

There is also a conditioned connection: a Poisson(1) offspring tree conditioned to have $n$ vertices, with offspring order forgotten and labels assigned uniformly with a fixed root label, gives a uniform labeled rooted tree. The conditioning changes the distribution and cannot be discarded when comparing it with the local exploration of $G(n,1/n)$.

Exercise. For Poisson offspring of mean $0.8$, compute the expected total progeny. For the Prüfer word 232 on five vertices, find the degree of vertex 2. Hint: use the geometric series and the occurrence count. Solution: the expected progeny is 5, and vertex 2 has degree 3.

23.7 Random permutations and partitions

A uniform random permutation of $[n]$ gives each of the $n!$ bijections probability $1/n!$. Let $C_k$ count its cycles of length $k$. Choose the $k$ vertices of a cycle, arrange them cyclically in $(k-1)!$ ways, and permute the rest in $(n-k)!$ ways. Indicators then give

$$ \mathbb E C_k=\binom nk\frac{(k-1)!(n-k)!}{n!}=\frac1k. $$

Thus the expected total cycle count is $H_n=\sum_{k=1}^n1/k$. For any fixed collection of lengths, their counts tend jointly to independent Poisson variables with respective means $1/k$; this is an asymptotic statement. At finite $n$, the constraint $\sum_k kC_k=n$ couples them.

Solved permutation. The permutation $(1\ 2\ 3)(4\ 5)(6)$ has three cycles, with $C_1=C_2=C_3=1$. For a uniform permutation on six labels, the expected cycle count is $H_6=49/20$, which is not the count of every permutation.

A set partition of $[n]$ is a collection of nonempty, disjoint blocks covering $[n]$. The uniform distribution gives each of the $B_n$ set partitions equal weight, where $B_n$ is the Bell number. If $m_j$ blocks have size $j$, then $\sum_j jm_j=n$ and the number of partitions with that block profile is

$$ \frac{n!}{\prod_j (j!)^{m_j}m_j!}. $$

The denominators remove order inside each block and order among equal-sized blocks. An integer partition records only the sizes and has a different natural uniform distribution.

Solved distribution on four labels. There are 15 set partitions.

The expected block count is $(1+8+6+18+4)/15=37/15$. Uniformly choosing one of the five integer partitions of 4 would assign each profile probability $1/5$, unlike these weights. Choosing a block count uniformly first also fails to produce the uniform set-partition model.

Exercise. What is the probability that a uniform set partition of $[4]$ has two blocks? Hint: combine the two relevant profiles. Solution: $(4+3)/15=7/15$.

23.8 Random hypergraphs

For fixed $r\ge2$, the model $H_r(n,p)$ includes each $r$-subset of $[n]$ independently with probability $p$. The fixed-size counterpart chooses $m$ distinct hyperedges uniformly. In the independent model,

$$ \mathbb E|E|=\binom nrp,\qquad d(v)\sim\operatorname{Bin}\left(\binom{n-1}{r-1},p\right). $$

We use ordinary vertex connectivity: vertices are connected when a chain of hyperedges joins them through overlapping vertices. This is not tight connectivity, which requires stronger overlaps of consecutive hyperedges.

Solved four-vertex case. In $H_3(4,1/2)$, the four possible triples are independent choices. With zero edges there are four isolated vertices; with one edge, a three-vertex component and one isolated vertex; with at least two edges, all four vertices are connected because any two distinct triples cover all four and intersect. Hence

$$ \Pr(\text{connected})=\Pr(\operatorname{Bin}(4,1/2)\ge2)=\frac{11}{16}. $$

The expected number of edges is 2, and the expected number of isolated vertices is $4(1/2)^3=1/2$. This exact small example does not establish a general threshold.

For sparse models, write $p=\lambda/\binom{n-1}{r-1}$, so the expected incident-edge count is $\lambda$. Each newly encountered hyperedge can reveal $r-1$ new vertices. The early-exploration reproduction mean is therefore $(r-1)\lambda$, rather than $\lambda$ alone. Its approximation has offspring count $(r-1)Y$, with $Y\sim\operatorname{Poisson}(\lambda)$, and generating function

$$ f(s)=\exp\bigl(\lambda(s^{r-1}-1)\bigr). $$

The branching prediction is a transition at $\lambda=1/(r-1)$, and an extinction equation $q=f(q)$. Established giant-component results justify this prediction with additional exploration and concentration arguments; a primary treatment is Bollobás and Riordan, Asymptotic normality of the size of the giant component in a random hypergraph. The full global proof is omitted here.

Exercise. In uniformity 3, what incident-edge mean corresponds to branching mean 1? Hint: one edge can reveal two new vertices. Solution: $\lambda=1/2$. Setting expected vertex degree to 1 instead gives branching mean 2 and is not the graph-like critical normalization.

23.9 Random constraint-satisfaction problems

Optional research extension. A constraint-satisfaction problem chooses values for variables so that every specified constraint is met. Random models sample the constraints from a stated distribution. A satisfiability transition concerns whether a solution exists, not whether a particular search algorithm finds it quickly.

For a precise random $k$-SAT model, use $n$ Boolean variables and $m$ independently sampled clauses. Each clause chooses $k$ distinct variables uniformly, then independently chooses the sign of each literal. A clause is the disjunction of those literals; the formula is the conjunction of all clauses. Sampling is with replacement across clauses, so repeated clauses are permitted. Let $Z$ count satisfying assignments.

A fixed assignment falsifies a random clause with probability $2^{-k}$. Independence across sampled clauses gives

$$ \mathbb E Z=2^n(1-2^{-k})^m. $$

With $m=\lfloor\alpha n\rfloor$, if

$$ \alpha\gt\frac{\log2}{-\log(1-2^{-k})}, $$

the expectation tends to zero exponentially, and Markov proves unsatisfiability w.h.p. For $k=3$, this elementary sufficient upper estimate is about $5.1909$. It is not the exact threshold or a best-current bound. A large expected solution count on the other side does not by itself prove satisfiability, because satisfying assignments can cluster and their indicators are dependent.

Solved finite formula. On variables $x,y,z$, take all eight sign patterns of the clause $\ell_x\vee\ell_y\vee\ell_z$. Each assignment falsifies exactly one of those clauses, so their conjunction is unsatisfiable. Delete one clause: its unique falsifying assignment now satisfies every remaining clause, giving exactly one solution. This exhausts a small deterministic formula; it is not a threshold calculation for large random formulas.

Established theorem and proof mechanism. Ding, Sly, and Sun, Proof of the satisfiability conjecture for large k, published in the Annals of Mathematics in 2022, identifies a limiting threshold $\alpha_*(k)$ for all sufficiently large fixed $k$. Below it, satisfiability holds w.h.p.; above it, unsatisfiability holds w.h.p. The proof analyzes a structured solution count and tree recursions to control correlations, using ideas motivated by statistical physics. The moment optimization and replica-symmetry-breaking framework are omitted prerequisites; this is a proof-mechanism summary, not a proof of the theorem.

Research snapshot, checked 11 October 2026. Two newly posted primary preprints report further results. Carenini, A polynomial scaling window for random k-SAT and a proof of the satisfiability conjecture, posted 5 October 2026, reports a proof of a limiting threshold for every fixed $k\ge3$. Vorobyev, An upper bound of 4.268 for the random 3-SAT satisfiability threshold, submitted 6 October 2026, reports unsatisfiability w.h.p. with $\lfloor4.268n\rfloor$ clauses. These are dated preprint reports, distinct from the earlier published large-$k$ theorem. Existence of a limiting threshold and an upper bound on its value are different conclusions; neither the elementary first moment nor the reported numerical upper bound gives an exact 3-SAT threshold value.

Exercise. Why does $\mathbb E Z\gt1$ fail to prove that most formulas are satisfiable? Hint: compare an average with a success probability. Solution: a small fraction of formulas can contribute very large solution counts while most have zero. Controlling correlations or another construction argument is needed.

23.10 Local weak convergence and random-structure limits

Optional advanced elective. Section 47.6 is recommended later background for limits of random structures; it is not an entry requirement here. The bridge is to examine a fixed-radius neighborhood around a uniform random vertex before asking about the whole graph. A full primary treatment in sparse graph models is Bordenave and Caputo, Large deviations of empirical neighborhood distribution in sparse random graphs.

For a graph $G$ rooted at $o$, let $B_R(G,o)$ be the induced rooted graph on vertices at graph distance at most $R$ from $o$. A sequence with uniform random roots converges locally weakly to a random rooted, locally finite graph if, for each fixed $R$, these neighborhood distributions converge. Root-preserving isomorphism matters; the original vertex labels do not. The radius stays fixed while the graph size grows.

Solved deterministic limit. In the cycle $C_n$, if $n\gt2R+1$, every radius-$R$ ball is a path of $2R+1$ vertices rooted at its middle. Hence the locally weak limit is the infinite path extending in both directions. The whole finite cycle is not itself a tree, yet every fixed-radius ball eventually is.

For $G(n,c/n)$, the local weak limit is a Poisson($c$) Galton–Watson tree. The root degree tends to Poisson($c$), as calculated in Section 23.4. During exploration of a fixed neighborhood, newly exposed degrees have the same approximate offspring law and collisions disappear in the limit. To make this rigorous, truncate the exploration at a fixed large number of discovered vertices, bound its collision probability by $O(1/n)$ at that truncation, and then control the probability of exceeding the truncation. This supplies a proof mechanism; the tightness and coupling details are omitted.

Uniform simple $d$-regular graphs, for fixed $d\ge2$, instead have the infinite $d$-regular tree as their local limit: the root has $d$ neighbors, and each newly reached vertex has $d-1$ further neighbors. Their local degrees do not become Poisson. Uniform labeled trees require conditioning as discussed in Section 23.6; their limiting root degree already rules out an unconditioned Poisson(1) offspring limit.

What a local limit cannot determine. Compare one cycle $C_n$ with two disjoint cycles of length $n/2$, for even $n$. Both have the same infinite-path local limit, but one is connected and the other is not. Each graph has edge density tending to zero and degree exactly two. Even matching local neighborhoods and degrees does not identify global connectivity.

Dense graph limits ask different questions, such as subgraph densities on large vertex samples. They should not be substituted for local neighborhood limits without a bridge between the regimes. The sparse model $p=c/n$ has order $n$ edges, while fixed positive $p$ gives order $n^2$ edges and a growing root degree.

Exercise. What is the root degree in the local limit of a uniform 3-regular graph, and how many new neighbors does a nonroot vertex have? Hint: account for the edge to its parent. Solution: the root degree is 3, and each nonroot vertex has two further neighbors. A Poisson(3) root law would describe a different model.

Simulate a threshold and compare data with a rigorous probability estimate

The investigation separates a component-size transition from a connectivity transition, and separates Monte Carlo error from finite-size error. The sample mean estimates a finite-$n$ model; the limiting formulas describe a sequence as $n$ grows. Increasing the number of samples reduces sampling error but does not turn a finite graph into an infinite one.

Completed simulation procedure. The following tables were computed using NumPy 2.3.5, default_rng with seed 2026101123. For every graph, unordered pairs are enumerated in upper-triangular order and receive fresh independent uniform draws; include a pair exactly when its draw is below $p$. Union-find computes components, and endpoint counts compute degrees and isolation. The generator is used continuously: component runs first, in increasing $n$ and then the listed $c$ order; connectivity runs next in increasing $t$ order. Independent graph draws are used across replicates, rather than reusing one coupled realization.

Observed component sizes. Entries are mean largest-component fractions, rounded to four decimals. The limit column solves $\rho=1-e^{-c\rho}$, using zero for $c\le1$.

The subcritical fractions decrease as $n$ increases; at $c=1$, a substantial finite fraction can still occur even though its limiting fraction is zero. The supercritical values near 1 retain noticeable finite-size effects, and individual batches need not move monotonically toward the limit. At $c=2$, the observed fraction is close to the positive solution, about $0.7968$.

Observed connectivity. The middle probability column is the number of connected graphs divided by 1000. The isolated expectation is exact for finite $n$; the last column is an asymptotic prediction.

Finite probability bounds, with proof. Let $P_n(p)$ be the exact probability of connectivity, and put

$$ \mu=n(1-p)^{n-1},\qquad \nu=n(n-1)(1-p)^{2n-3},\qquad B=\sum_{k=1}^{\lfloor n/2\rfloor}\binom nk(1-p)^{k(n-k)}. $$

The cut union bound gives $P_n(p)\ge\max(0,1-B)$. Since $\mathbb E[I^2]=\mu+\nu$, the second-moment method gives $\Pr(I\gt0)\ge\mu^2/(\mu+\nu)$. Connectivity requires $I=0$, hence

$$ \max(0,1-B)\le P_n(p)\le1-\frac{\mu^2}{\mu+\nu}. $$

At $n=200,t=2$, $p\approx0.0364916$. Evaluating these expressions gives, with outward rounding,

$$ 0.8690\le P_{200}(p)\le0.8913. $$

The measured frequency $0.886$ lies in this interval. That observation agrees with the bounds, but the bounds concern the true finite-model probability, not a guarantee that every sample frequency lies inside them. The limiting value $0.8734$ is a separate comparison and does not supply a finite-$n$ error bound.

Sampling uncertainty. For $R$ independent graphs, the connectivity indicators are independent Bernoulli variables. Hoeffding gives

$$ \Pr(|\widehat P-P_n(p)|\ge\eta)\le2e^{-2R\eta^2}. $$

A union bound over the five connectivity parameters, with $R=1000$, makes all five estimation errors at most

$$ \eta=\sqrt{\frac{\log(2\cdot5/0.05)}{2\cdot1000}}\approx0.0515 $$

with probability at least $0.95$ over the experiment. Clip corresponding intervals to $[0,1]$. For component fractions, the same bounded-variable inequality controls each sample mean around its finite-$n$ expectation; it does not control the distance from that expectation to $\rho(c)$.

Connection and application. At fixed $c$, the degree distribution and early BFS neighborhoods approach a Poisson($c$) branching tree, connecting $G(n,p)$ to the local limit. The giant fraction is a global survival phenomenon, while connectivity also requires isolated vertices and every other component to disappear. An independently connected communication network can use these models as a baseline for component formation or robustness under random link failures. Spatial constraints, unequal link probabilities, or correlated failures would change the model and may change its thresholds; state those assumptions before using the estimate.

Optional extension. Reuse one set of edge scores across parameters to visualize monotone merging, but keep independent graph replicates for each probability estimate and account for dependence between parameter estimates. Alternatively, test local balls against the branching-process prediction or compare one large cycle with two cycles to demonstrate a common local limit and different connectivity. These are finite, reproducible investigations; they are not assertions of unresolved research problems.