Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 1 / 17F / b / iii / Solution

For odd $s$, place $2s-1$ vertices cyclically. Color red the edges of cyclic differences $\pm 1,\dots ,\pm (s-1)/2$, and blue every other edge. Each red degree is $s-1$, and each blue degree is also $(2s-2)-(s-1)=s-1$. There is no monochromatic $K_{1,s}$. For $s=1$ the same lower bound is the single-vertex graph. Together with the previous upper bound, this proves