Breadth-first exploration of a binomial random graph ($U_t=(1-p)(U_{t-1}-b_t)-D_t$)

During Breadth-first search of $G(n,p)$ let $U_t$ count unseen vertices, $A_t$ active vertices, and $t$ explored vertices. When $A_{t-1}=0$ start a new unseen root, recorded by $b_t=1$; otherwise $b_t=0$. The newly discovered count is conditionally $\mathrm{Bin}(U_{t-1}-b_t,p)$. Subtract its conditional mean to obtain a martingale difference $D_t$. With $q=1-p$, $U_0=n$ and $A_0=0$, iteration givesThe last sum is a martingale. Positive $A_t$ over an interval means that the graph component under exploration does not finish there. Independently adding phantom children couples each component exploration below a binomial branching process with offspring law $\mathrm{Bin}(n,p)$.