[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)$.[/step]

[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: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.[/step]

[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: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]