Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 339 / 2 / c / iv

If $m=0$, use a single color. Otherwise chooseThe previous bound gives $\mathbb{E}B\le n/4$, including the case $r=0$. By Markov inequality, $\mathbb{P}(B>n/2)\le 1/2$. Sample the hyperplanes, count the monochromatic edges, and repeat if $B>n/2$. The success probability is at least $1/2$, so at most two draws are needed on average.

For a successful draw, select one endpoint of each monochromatic edge and let $D$ be the union of the selected vertices. Then $|D|\le B\le n/2$. Every monochromatic edge meets $D$, so the original colors give a proper graph colouring on the induced subgraph with vertex set $W=V\setminus D$. Since $|W|\ge n/2$, the coloring of all vertices is a semicoloring. This is a random alteration method; no additional colors for $D$ are required.

The number of available colors satisfies $2^r\le 2\max \{1,(4m/n{)}^{{\log }_{3}2}\}$. A simple graph has $m\le n(n-1)/2$, hence semicoloring by independent hyperplanes gives