Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / B / 7

Explore the component of one vertex by processing discovered vertices in order. At each step, the number of newly discovered neighbours is a binomial variable with at most $n$ trials and success probability $1/(2n)$, on previously unexposed independent edges. Pad each step with independent dummy trials. This couples the exploration below independent offspring variables ${\xi }_i\sim \mathrm{Bin}(n,1/(2n))$, each of mean one half.

If the component has at least $k\ge 2$ vertices, after $k-1$ vertices have been processed at least $k-1$ offspring must have been found. HenceThe sum is binomial with mean $\mu =(k-1)/2$. The multiplicative Chernoff inequality $P(B\ge 2\mu )\le (e/4{)}^{\mu }$ therefore givesA union bound over all vertices bounds the probability of any component of size at least $k$ by $n{e}^{-c(k-1)}$. Taking $k=\lceil \alpha {\log }_{e}n\rceil$ with any $\alpha >1/c$, for example ten, makes this tend to zero. Thus the largest component is at most a constant times $\log n$ with high probability.

Every vertex in the component can be reached from $v$ by a simple path. The number of potential length-$\ell$ simple paths beginning at $v$ is at most $n^{\ell }$, and each has probability $(1/(2n){)}^{\ell }$ of being present. Counting such paths may count a vertex more than once, so it gives an upper bound on the expected number of reached vertices:Thus $\boxed{K=2}$ works for every $n$. Equivalently the dominating branching process has mean offspring one half and expected total progeny two.