= Solution
Fix a proper <colouring> with exactly $k$ nonempty <colour classes>. For any class $C_i$, suppose every <vertex> in it misses at least one of the other $k-1$ colours in its <neighbourhood>. Recolour each of these <vertices> by one of its missing colours. No <edge> joins two <vertices> of $C_i$, so these simultaneous recolourings cannot conflict with one another, and the chosen colours do not conflict with <vertices> outside $C_i$.
This would eliminate colour $i$ and produce a $(k-1)$-colouring, contradicting optimality. Therefore each <colour class> contains a <vertex> adjacent to at least one <vertex> of every other colour. That <vertex> has degree at least $k-1$. Choosing one from each class gives $k$ distinct <vertices>, proving
$$
\boxed{\bigl|\{v:\deg(v)\geq k-1\}\bigr|\geq k.}
$$
For $k=1$, a nonempty <graph> already has a <vertex> of degree at least zero, so the conclusion holds as well.
Back to article page
