We may assume $G$ is 2-connected (otherwise, color blocks independently). Also assume $\Delta \geq 3$ (the case $\Delta \leq 2$ is trivial or follows from the cycle exception).

Case 1: $G$ is not $\Delta$-regular. There exists a vertex $v$ with $\deg(v) < \Delta$. Order the vertices by BFS starting from $v$, and apply greedy coloring in reverse BFS order. Each vertex (except $v$) has at most $\Delta - 1$ already-colored neighbors when processed (since at least one neighbor appears later in BFS). The vertex $v$ is colored last and has $< \Delta$ neighbors, so $\Delta$ colors suffice.

Case 2: $G$ is $\Delta$-regular and not complete. Since $G$ is not complete, there exist two non-adjacent vertices $u, w$ that share a neighbor $v$ (this uses 2-connectivity and regularity). We construct a special ordering: let $v_1 = u$, $v_2 = w$, and order the remaining vertices so that each $v_i$ ($i \geq 3$) has at least one neighbor among $v_{i+1}, \ldots, v_n$ and $v_n = v$.

To build this ordering: take $v_n = v$. Since $G - \{u, w\}$ is connected (by 2-connectivity and the non-adjacency of $u, w$), order $v_3, \ldots, v_{n-1}$ by reverse BFS from $v$ in $G - \{u, w\}$.

Now apply greedy coloring in the order $v_1, v_2, \ldots, v_n$:

• $v_1 = u$: assign color 1.
• $v_2 = w$: assign color 1 (same as $u$; this is valid since $u$ and $w$ are not adjacent).
• $v_3, \ldots, v_{n-1}$: each has at most $\Delta - 1$ previously colored neighbors (at least one neighbor comes later), so a color from $\{1, \ldots, \Delta\}$ is always available.
• $v_n = v$: has $\Delta$ neighbors, but $u$ and $w$ share the same color, so at most $\Delta - 1$ distinct colors appear among $v$'s neighbors. A color is available.

In all cases, $\Delta$ colors suffice. $\square$