= 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 count
$$
\frac23e(G).
$$
Some colouring therefore retains at least $2e(G)/3$ edges. Its retained <subgraph> is three-colourable, and deleting edges if necessary leaves exactly
$$
\boxed{\left\lfloor\frac23e(G)\right\rfloor}
$$
edges 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 set>[independent sets], so
$$
e(H)\leq n_1n_2+n_1n_3+n_2n_3
=\frac12\left(n^2-\sum_i n_i^2\right)
\leq\frac{n^2}{3},
$$
where the final inequality follows from <Cauchy-Schwarz inequality>. Since $e(K_n)=n(n-1)/2$,
$$
\frac{e(H)}{e(K_n)}\leq\frac{2n}{3(n-1)}
=\frac23+\frac{2}{3(n-1)}.
$$
Given $\varepsilon>0$, choose $n$ with $2/[3(n-1)]\leq\varepsilon$. Then every three-colourable subgraph has at most $(2/3+\varepsilon)e(G)$ edges.
Back to article page
