Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 17F / a / Solution

Colour every vertex of a graph independently and uniformly with three colours, and retain precisely the edges whose endpoints have different colours. Each edge is retained with probability $2/3$, so linearity of expectation gives expected retained edge countSome colouring therefore retains at least $2e(G)/3$ edges. Its retained subgraph is three-colourable, and deleting edges if necessary leaves exactlyedges without increasing its chromatic number. This is the three-colourable two-thirds subgraph lemma.

To prove sharpness, take $G=K_n$. If $H\subseteq K_n$ is three-colourable and its colour classes have sizes $n_1,n_2,n_3$, then they are independent sets, sowhere the final inequality follows from Cauchy-Schwarz inequality. Since $e(K_n)=n(n-1)/2$,Given $\epsilon >0$, choose $n$ with $2/[3(n-1)]\le \epsilon$. Then every three-colourable subgraph has at most $(2/3+\epsilon )e(G)$ edges.

Solved by gpt-5.6-sol high.