Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 4 / 17H (Graph Theory)

Let $d_v$ be the vertex degrees and let $r_{ij}$ count common neighbours of distinct vertices. Count unoriented length-two paths by their centre or endpoints:If no four-cycle occurs, $r_{ij}\le 1$, so $P_2\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$. By Cauchy-Schwarz inequality, $P_2\ge \frac{1}{2}[(2m{)}^2/n-2m]$. Solving $4m^2-2nm\le n^2(n-1)$ givesIf $m\ge n(n-1)/4$, the same bound and monotonicity of $2m^2/n-m$ in this range give $P_2\ge n(n-1)(n-3)/8$ (the small $n$ cases are immediate). Every pair of common neighbours supplies a four-cycle, counted twice through its two opposite vertex pairs, so four-cycle counting by common neighbours givesLet $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $\bar{r}=P_2/N\ge (n-3)/4$. Convexity of $r(r-1)/2$ gives $C_4\ge (N/2)\left(\genfrac{}{}{0ex}{}{\bar{r}}{2}\right)$. For $n\ge 7$, this function is increasing on the needed range, givingFor $3\le n\le 6$ the printed right-hand side is nonpositive and the conclusion is trivial. At $n=2$ the printed cycle bound is false: a single edge meets the edge hypothesis but has no four-cycles, while the right-hand side is $5/64>0$. Thus this particular bound needs the intended $n\ge 3$ restriction; the other counting statements above do not have this defect.

On four chosen vertices there are three distinct cycle subgraphs, each present with probability $2^{-4}$ in the stated random graph. Extra edges do not destroy these subgraphs. ThereforeFor positive expectation, Markov inequality giveswhen $0<ϵ<1/2$. If $n<4$, the cycle count is identically zero and the requested event has probability one.