The greedy colouring bound $\chi(G)\leq\Delta(G)+1$ for every nonnull finite graph

For each $i<n$, at most $\deg_G(v_i)\leq\Delta(G)$ earlier neighbours of $v_i$ have already been considered. If all $\Delta(G)+1$ colours occurred among them, choosing for each colour its least earlier-neighbour index would inject the $\Delta(G)+1$ colours into a set of at most $\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)\ne c(v_i)$. Thus $c$ is a proper $(\Delta(G)+1)$-colouring.

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