The greedy colouring bound $\chi (G)\le \mathrm{\Delta }(G)+1$ for every nonnull finite graph

For each $i<n$, at most ${\mathrm{deg}}_G(v_i)\le \mathrm{\Delta }(G)$ earlier neighbours of $v_i$ have already been considered. If all $\mathrm{\Delta }(G)+1$ colours occurred among them, choosing for each colour its least earlier-neighbour index would inject the $\mathrm{\Delta }(G)+1$ colours into a set of at most $\mathrm{\Delta }(G)$ indices, contradicting [L3]. Thus at least one colour is absent.

Let $P(i)$ say that either $n<i$, or the first $i$ vertices have a unique colouring which uses the least available colour at every vertex. The empty colouring verifies $P(0)$.

Assume $P(i)$. If $n<i$ or $i=n$, then $n<i+1$, so $P(i+1)$. If $i<n$, step 1.1 gives a nonempty set of available colours for $v_i$, and [L4] gives its unique least element. Appending that colour to the unique preceding colouring produces the unique greedy colouring of the first $i+1$ vertices; hence $P(i+1)$. These cases are exhaustive by [L5].

Induction using steps 1.2 and 2.1 gives $P(n)$. Since $n<n$ is false, this gives a greedy colouring $c$ of all $n$ vertices.

If $\{v_i,v_j\}\in E$ with $i<j$, then $v_i$ is an earlier neighbour of $v_j$, so the rule in step 3.1 gives $c(v_j)\mathrm{\ne }c(v_i)$. Thus $c$ is a proper $(\mathrm{\Delta }(G)+1)$-colouring.

Since such a colouring exists, the minimality clause in [L1] gives $\chi (G)\le \mathrm{\Delta }(G)+1$.