Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 17G (Graph Theory)

The binomial random graph $G(n,p)$ has vertex set $[n]=\{1,\dots ,n\}$, and each unordered pair of distinct vertices is included as an edge independently with probability $p$.

Let $X_t$ count copies of the complete graph $K_t$. Each $t$-element vertex set forms a copy with probability $p^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$, so linearity of expectation givesThe event $E_t$ is $\{X_t\ge 1\}$. By the first moment method,This is the clique count in a binomial random graph.

Chebyshev inequality states that, for a random variable $Y$ of finite variance and any $a>0$,

Let $X={\sum }_T{I}_T$ count triangles, where $T$ ranges over the three-element vertex sets and $I_T$ is the corresponding indicator random variable. ThenTwo distinct triangle indicators are independent unless their triangles share an edge. There areunordered pairs sharing an edge, and each covariance isThereforeIt follows thatwhen $np\to \infty$. Chebyshev's inequality now givesHenceas summarized by the triangle count in a binomial random graph.

Partition the vertex set into disjoint sets $A$ and $B$ of sizes $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$. The induced subgraph on $A$ has distributionFor $p=n^{-0.9}$,so part (b) shows that $A$ contains a triangle with probability tending to one.

On that event, choose a triangle using only the edges internal to $A$. The edges from its three vertices to $B$ remain independent of this choice. The probability that all $3|B|$ such edges are absent isbecause $p|B|\sim n^{0.1}/2$. Thus, with probability tending to one, some vertex of $B$ is adjacent to a vertex of the triangle. Those four vertices and the four required edges form the given graph $H$, a triangle with an attached leaf in a binomial random graph. Therefore