Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 36 / 2 / b

For a nonnegative integer-valued random variable, $1_{\{X>0\}}\le X$ pointwise. Taking expectations givesThis is the indicator form of the Markov inequality.

Let $I_{ij}$ be the indicator random variable that the unordered vertex pair $\{i,j\}$ has no common neighbour. For each of the other $n-2$ vertices, the two required edges are both present with probability $p^2$. The edge pairs for different candidate neighbours are disjoint sets of independent random choices. Thus $\mathbb{E}{I}_{ij}=(1-p^2{)}^{n-2}$. Linearity of expectation yieldsthe missing common-neighbour count in a binomial random graph.

If $X=0$, every pair of vertices has a common neighbour, so every pair has graph distance at most two. In particular the graph is connected and its graph diameter is at most two. By the Markov inequality and part (ii),We include disconnected graphs among those with diameter greater than two. Thereforeby diameter bound for a fixed-density binomial random graph.