Connectivity hitting time equals disappearance of isolated vertices
ID: connectivity-hitting-time-equals-disappearance-of-isolated-vertices
Couple the process with independent uniform edge labels, and expose . A spanning-tree union bound excludes components of orders through , and a cut bound excludes orders up to . The graph has one large component and at most isolated vertices, with at least one isolated vertex. Before , the probability of any new edge between those isolated vertices is . All have joined the large component by 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.
New to topics? Read the docs here!