[proofplan] We construct an ordering of the vertices of $G$ under which the greedy algorithm uses at most $\Delta(G)$ colours. The key idea is to place a low-degree vertex $x_n$ with $\deg x_n < \Delta(G)$ last, and order the remaining vertices by a reverse breadth-first traversal rooted at $x_n$. Under this ordering, every vertex $x_i$ with $i < n$ has at least one neighbour that appears later in the ordering (namely, its parent in the BFS tree), so the number of its predecessors among its neighbours is at most $\deg x_i - 1 \leq \Delta(G) - 1$. The final vertex $x_n$ has $\deg x_n \leq \Delta(G) - 1$ predecessors by its low-degree hypothesis. Greedy colouring with this predecessor bound uses at most $\Delta(G)$ colours. [/proofplan] [step:Pick a vertex of deficient degree and order by reverse BFS] By hypothesis $\delta(G) < \Delta(G)$, so there exists $x_n \in V(G)$ with $\deg x_n < \Delta(G)$, i.e., $\deg x_n \leq \Delta(G) - 1$. Since $G$ is connected, a breadth-first search rooted at $x_n$ visits every vertex of $G$. Let $y_1 = x_n, y_2, y_3, \ldots, y_n$ denote the vertices in the order they are first discovered by this BFS, so that each $y_j$ with $j \geq 2$ is adjacent in $G$ to some $y_k$ with $k < j$ (its BFS parent). Define the reverse BFS ordering \begin{align*} x_1 := y_n, \quad x_2 := y_{n-1}, \quad \ldots, \quad x_{n-1} := y_2, \quad x_n := y_1. \end{align*} The defining property of this ordering is: *Parent-later property.* For each $i \in \{1, 2, \ldots, n - 1\}$, the vertex $x_i$ has at least one neighbour among $\{x_{i+1}, x_{i+2}, \ldots, x_n\}$. This holds because $x_i = y_{n+1-i}$ has a BFS parent $y_k$ with $k < n + 1 - i$, and $y_k = x_{n+1-k}$ with $n + 1 - k > i$, so the parent appears in the ordering as $x_{n+1-k}$ with index $n + 1 - k > i$. [guided] We need to choose a vertex ordering of $G$ such that, when the greedy algorithm processes vertices in this order, every vertex sees at most $\Delta(G) - 1$ already-coloured neighbours. Such an ordering would let greedy use the first colour not yet used among the neighbours, which is at most the $\Delta(G)$th colour. The hypothesis $\delta(G) < \Delta(G)$ gives us a vertex of strictly deficient degree. Pick any $x_n \in V(G)$ with $\deg x_n \leq \Delta(G) - 1$. This will be the *last* vertex in our ordering — strategically placed because its own predecessor count is automatically bounded by its (small) degree, regardless of how we arrange its neighbours. For the other vertices we use connectivity. Since $G$ is connected, we can run a breadth-first search from $x_n$; it visits every vertex. Let $y_1 = x_n, y_2, \ldots, y_n$ denote the BFS discovery order, so each $y_j$ for $j \geq 2$ has some already-visited neighbour $y_k$ with $k < j$ (its BFS parent). Now **reverse** this order: define the greedy ordering to be \begin{align*} x_1 := y_n, \quad x_2 := y_{n-1}, \quad \ldots, \quad x_{n-1} := y_2, \quad x_n := y_1. \end{align*} Why reverse? Because we want each non-final vertex $x_i$ to have a neighbour *later* in the greedy ordering (this neighbour will not count as a predecessor, so the predecessor count is at most $\deg x_i - 1$). In BFS the parent is *earlier* than the child; reversing turns "parent earlier" into "parent later", which is exactly what we want. Concretely, for each $i \in \{1, \ldots, n-1\}$, the vertex $x_i = y_{n+1-i}$ has a BFS parent $y_k$ with $k < n + 1 - i$. Under reversal this parent becomes $x_{n+1-k}$, and $n + 1 - k > i$ (because $k < n + 1 - i$), so the parent's index in the greedy ordering exceeds $i$. This is the *parent-later property*: $x_i$ has a neighbour in $\{x_{i+1}, \ldots, x_n\}$. [/guided] [/step] [step:Run the greedy algorithm with this ordering] Let $[t] := \{1, 2, \ldots, \Delta(G)\}$ be a palette of $\Delta(G)$ colours. Process vertices in the order $x_1, x_2, \ldots, x_n$. For each $x_i$, assign the smallest colour in $[t]$ that does not appear on any already-coloured neighbour $x_j$ with $j < i$. We call this the *greedy colouring* $c: V(G) \to [t]$. We must verify that at each step a colour from $[t]$ is available. *For $i \in \{1, 2, \ldots, n - 1\}$*: by the parent-later property, $x_i$ has at least one neighbour among $\{x_{i+1}, \ldots, x_n\}$. The number of neighbours of $x_i$ among its predecessors $\{x_1, \ldots, x_{i-1}\}$ is therefore at most $\deg x_i - 1 \leq \Delta(G) - 1$. Hence at most $\Delta(G) - 1$ colours of $[t]$ are forbidden when colouring $x_i$, leaving at least one available colour in $[t]$. *For $i = n$*: the vertex $x_n$ was chosen with $\deg x_n \leq \Delta(G) - 1$. Its predecessors among its neighbours number at most $\deg x_n \leq \Delta(G) - 1$, so at most $\Delta(G) - 1$ colours of $[t]$ are forbidden, leaving at least one available colour in $[t]$. In both cases the greedy step succeeds with a colour in $[t]$. By construction $c(u) \neq c(v)$ for every edge $uv \in E(G)$: if $u = x_i$ and $v = x_j$ with $i < j$, then $u$ was already coloured when $v$ was processed, and $c(v)$ was chosen to avoid $c(u)$. Therefore $c: V(G) \to [t]$ is a proper colouring using at most $\Delta(G)$ colours, giving $\chi(G) \leq \Delta(G)$. This completes the proof. [/step]