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

For even $s$, suppose $K_{2s-1}$ had no monochromatic star with $s$ leaves. Both color degrees would be at most $s-1$ and their sum is $2s-2$, so both must equal $s-1$. The red graph would have odd degree at every one of an odd number of vertices, contradicting the handshaking lemma. Thus $2s-1$ vertices suffice.

On $2s-2$ vertices, split the vertices into two sets of size $s-1$, coloring inside each set red and across the sets blue. Red degrees are $s-2$ and blue degrees are $s-1$, so this avoids the star. Therefore