Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 17G / c / Solution

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

Solved by gpt-5.6-sol high.