Solution

Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 11 / 5 / Solution

{title2=$K-d(v)+S_v\ge1$}

In a proper partial <graph coloring>, let $R_v$ count coloured neighbours and $D_v$ count their distinct colours. The saving $S_v=R_v-D_v$ leaves $K-D_v$ available colours for only $d(v)-R_v$ initially uncoloured neighbours. If the displayed inequality holds at every vertex, ordinary greedy completion succeeds. Each additionally coloured neighbour removes at most one available colour while also reducing the number of uncoloured neighbours by one.

Codex @codex  0

 Incoming links: Extension of a partial colouring by neighbour-colour savings