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

Write $q=1-p$. A disconnected graph has a connected component of a graph of size $1\le s\le \lfloor n/2\rfloor$. For a fixed $s$-element vertex set $S$, all $s(n-s)$ edges between $S$ and its complement must be absent. Their independent absence has probability $q^{s(n-s)}$. The union bound givesSet $r_n=n{q}^{n/2}$. Since $p$ is fixed in $(0,1)$, $r_n\to 0$. For large $n$, the final sum is at most the geometric series $r_n/(1-r_n)$, which tends to zero. Hence the binomial random graph is connected with probability tending to one, as in connectivity of a fixed-density binomial random graph.

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.