= Connectivity hitting time equals disappearance of isolated vertices
{title2=$\tau_{\rm conn}=\tau_{\delta\geq1}\text{ with high probability}$}
Couple the process with independent uniform edge labels, and expose $p_-=(\log n-\frac14\log\log n)/n$. A spanning-tree <union bound> excludes components of orders $2$ through $n/\log n$, and a cut bound excludes orders up to $n/2$. The graph has one large component and at most $\log n$ isolated vertices, with at least one isolated vertex. Before $p_+=(\log n+\frac14\log\log n)/n$, the probability of any new edge between those isolated vertices is $O((\log n)^2\log\log n/n)=o(1)$. All have joined the large component by $p_+$ by the <isolated-vertex threshold in the Erdős-Rényi model>. Throughout this window the only obstruction to connectivity is an isolated vertex, establishing the equality of hitting times.
Back to article page
