Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 12 / 1 / i

It suffices to find a tree component of order $k$. Let $X$ count such graph components in the binomial random graph. The Cayley formula and independent edges give the tree-component expectation in the Erdős-Rényi modelHere $k$ is fixed. The upper bound on $p$ implies $p=O(\log n/n)$, hence $n{p}^2=o(1)$ andWe first verify that this expected value diverges throughout the permitted interval, including when $\omega$ grows quickly. If $np\le 1$, the exponential factor is at least $e^{-k}$ and $n^k{p}^{k-1}\ge {\omega }^{k-1}$. If $1\le np\le (\log n)/(2k)$, then $n(np{)}^{k-1}{e}^{-knp}\ge \sqrt{n}$. Finally, if $np\ge (\log n)/(2k)$, the upper bound on $p$ givesThus $\mu \to \infty$ in all three cases.

For distinct $k$-element vertex sets $S,T$, write $I_S,I_T$ for their tree-component indicators. If they overlap, they cannot both be distinct connected components of a graph, so $\mathbb{E}(I_S{I}_T)=0$. If they are disjoint, the absent edges between the two sets are counted twice in the product of their marginal probabilities and once in the joint probability. ThereforeSumming and discarding the negative overlap contributions yieldsThe Chebyshev inequality now gives $\mathrm{Pr}(X=0)\le \mathrm{Var}X/{\mu }^2\to 0$. Consequently there is a component of order $k$ with high probability, in fact a tree component. The argument proves the entire fixed-order tree-component window, rather than only a particular choice of $p$.