[proofplan]
We exhibit an explicit proper $(\Delta(G) + 1)$-colouring of $G$ by the greedy algorithm. Fix an arbitrary ordering $x_1, \ldots, x_n$ of $V(G)$ and colour the vertices in that order using colours from $\{1, 2, \ldots, \Delta(G) + 1\}$, always assigning the smallest available colour not used by any already-coloured neighbour. The algorithm succeeds because when we reach $x_i$, at most $\deg(x_i) \leq \Delta(G)$ neighbours have been coloured, so they use at most $\Delta(G)$ of the $\Delta(G) + 1$ colours, leaving at least one free.
[/proofplan]
[step:Fix a palette of $\Delta(G) + 1$ colours and an arbitrary vertex ordering]
If $V(G) = \varnothing$ there is nothing to prove ($\chi(G) = 0 \leq \Delta(G) + 1$), so assume $V(G) \neq \varnothing$ and enumerate the vertices as $x_1, \ldots, x_n$ in any fixed order. Define the palette
\begin{align*}
\mathcal{C} := \{1, 2, \ldots, \Delta(G) + 1\},
\end{align*}
a set of $\Delta(G) + 1$ distinct colours. We will construct a proper colouring
\begin{align*}
c: V(G) &\to \mathcal{C}, \\
x_i &\mapsto c(x_i),
\end{align*}
meaning $c(u) \neq c(v)$ whenever $uv \in E(G)$.
[guided]
The greedy algorithm works with any ordering of the vertices. The bound $\Delta(G) + 1$ is insensitive to this choice — every ordering succeeds — and that is exactly what makes the bound so robust.
We fix the palette $\mathcal{C} = \{1, \ldots, \Delta(G) + 1\}$ in advance, which is valid since $\Delta(G) \geq 0$ always (with $\Delta(G) = 0$ corresponding to an edgeless graph, where $\chi(G) \leq 1$ directly). The claim we need is that any ordering $x_1, \ldots, x_n$ can be extended to a proper $\mathcal{C}$-colouring by colouring one vertex at a time.
[/guided]
[/step]
[step:Colour the vertices inductively via the greedy rule]
We define $c(x_i)$ by induction on $i \in \{1, \ldots, n\}$. For the inductive step, suppose $c(x_1), \ldots, c(x_{i-1})$ have already been defined, each assigned a value in $\mathcal{C}$, in such a way that $c(x_j) \neq c(x_{j'})$ whenever $x_j x_{j'} \in E(G)$ and $j, j' < i$.
Define the set of **forbidden colours** for $x_i$ as the colours used by the already-coloured neighbours of $x_i$:
\begin{align*}
F_i := \{c(x_j) : j < i, \; x_j x_i \in E(G)\}.
\end{align*}
Assign
\begin{align*}
c(x_i) := \min\bigl(\mathcal{C} \setminus F_i\bigr)
\end{align*}
(smallest colour in the palette not yet used by a coloured neighbour).
The key inequality is
\begin{align*}
|F_i| \leq \bigl|\{j : j < i, \; x_j x_i \in E(G)\}\bigr| \leq \deg_G(x_i) \leq \Delta(G),
\end{align*}
where the first inequality is because $F_i$ is the image of the set $\{j < i : x_j x_i \in E(G)\}$ under $j \mapsto c(x_j)$, the second is because this set is a subset of the neighbourhood $N(x_i)$, and the third is by definition of $\Delta(G)$. Hence
\begin{align*}
|\mathcal{C} \setminus F_i| \geq (\Delta(G) + 1) - \Delta(G) = 1,
\end{align*}
so $\mathcal{C} \setminus F_i \neq \varnothing$ and the minimum is well-defined.
[guided]
At step $i$ we have coloured $x_1, \ldots, x_{i-1}$ using colours from $\mathcal{C}$, respecting the proper colouring constraint on edges among the already-coloured vertices. Our job is to extend by choosing a colour $c(x_i) \in \mathcal{C}$ that respects edges between $x_i$ and its already-coloured neighbours.
Which colours are forbidden? Exactly the colours used by already-coloured neighbours of $x_i$ — the set $F_i = \{c(x_j) : j < i, x_j x_i \in E(G)\}$. If $c(x_i) \notin F_i$, then the new edge constraints $c(x_i) \neq c(x_j)$ for each neighbour $x_j$ with $j < i$ are all satisfied.
Is $\mathcal{C} \setminus F_i$ non-empty? We bound $|F_i|$ in three steps:
- $F_i$ is the image of the set $S_i := \{j < i : x_j x_i \in E(G)\}$ under the map $j \mapsto c(x_j)$. In particular $|F_i| \leq |S_i|$ (image of a finite set).
- $S_i \subseteq \{j : x_j \in N(x_i)\}$, so $|S_i| \leq |N(x_i)| = \deg_G(x_i)$.
- By definition of the maximum degree, $\deg_G(x_i) \leq \Delta(G)$.
Combining, $|F_i| \leq \Delta(G) < \Delta(G) + 1 = |\mathcal{C}|$. So $\mathcal{C} \setminus F_i$ has at least one element, and its minimum (under the natural ordering of $\{1, \ldots, \Delta(G) + 1\}$) is a valid colour for $x_i$.
[/guided]
[/step]
[step:Verify that the produced colouring is proper]
Let $uv \in E(G)$ with $u = x_j$, $v = x_i$, say $j < i$. By the construction in the previous step, $c(x_i) \in \mathcal{C} \setminus F_i$, and $c(x_j) \in F_i$ because $j < i$ and $x_j x_i \in E(G)$. Hence $c(x_j) \neq c(x_i)$, i.e., $c(u) \neq c(v)$.
Since this holds for every edge $uv \in E(G)$, the map $c: V(G) \to \mathcal{C}$ is a proper colouring of $G$. The palette has $|\mathcal{C}| = \Delta(G) + 1$ colours, so
\begin{align*}
\chi(G) \leq \Delta(G) + 1,
\end{align*}
as claimed.
[/step]
