Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 4 / b

Because $\chi (H)=3$, every bipartite graph is $H$-free. The balanced complete bipartite graph therefore gives

For the reverse bound, fix $\delta >0$ and suppose that $G$ has more than $(1/2+\delta )\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. Apply the Szemerédi regularity lemma with parameters much smaller than $\delta$. Form the reduced graph whose vertices are the regularity classes and whose edges are the regular pairs of density above a small fixed threshold. Edges inside classes, irregular pairs, and regular pairs below the threshold account for $o_{\delta }(n^2)$ edges. The remaining edges force the reduced graph to have more than $m^2/4$ edges.

By the Turan theorem, the reduced graph contains a triangle. The three corresponding regular pairs all have positive density, and the graph embedding lemma for regular pairs embeds every fixed three-colourable graph, in particular $H$, across suitable repeated subclusters of these three classes. Thus every sufficiently large graph of density above $1/2+\delta$ contains $H$. Letting $\delta \downarrow 0$ givesThis is the chromatic-number-three case of the Erdős-Stone theorem.