[proofplan] We prove $\chi(G) \leq \Delta(G)$ by strong induction on $|G|$. Low-$\Delta$ cases ($\Delta(G) \leq 2$) are handled directly: the connected graphs with maximum degree at most $2$ are paths and cycles, and the only exceptions to the inequality — $K_2$ and odd cycles — are excluded by hypothesis. The inductive argument assumes $\Delta(G) \geq 3$ and splits on the vertex connectivity $\kappa(G)$. If $\kappa(G) \geq 3$ we use the shared-colour trick: a maximum-degree vertex $x_n$ has two non-adjacent neighbours $x_1, x_2$ (else $G = K_{\Delta(G)+1}$), and a greedy colouring in the order $x_1, x_2, \text{reverse-BFS tail}, x_n$ uses only $\Delta(G)$ colours because $x_1$ and $x_2$ share a colour. If $\kappa(G) = 1$, a cut vertex $z$ decomposes $G$ into pieces $G_i$ each strictly smaller with $\deg_{G_i}(z) < \Delta(G)$; the induction applies to each piece, and the colourings are glued by permuting palettes so that $z$ matches. If $\kappa(G) = 2$ with $2$-separator $\{x, y\}$, we add the edge $xy$ to each piece and handle the generic sub-case ($\delta(G_i) < \Delta(G)$ for all $i$) directly; the non-generic sub-case (some $\delta(G_i) = \Delta(G)$) is reduced to the generic one by switching to a new $2$-separator $\{x, y'\}$ where $y'$ is the unique neighbour of $y$ in $C_2$ — forced by a degree count — and verifying that $\delta < \Delta(G)$ for both new pieces. [/proofplan] [step:Dispose of the low-$\Delta$ cases, reducing to $\Delta(G) \geq 3$] We first handle $|G| = 1$ and $\Delta(G) \leq 2$ directly. *Case $|G| = 1$.* A single vertex is $K_1$, a complete graph. This is excluded by the hypothesis "$G$ is not a complete graph." Hence $|G| \geq 2$. *Case $\Delta(G) = 0$.* Every vertex has degree $0$, so $G$ has no edges. Combined with $|G| \geq 2$ and connectedness, this is a contradiction (two isolated vertices cannot be connected). So $\Delta(G) \geq 1$. *Case $\Delta(G) = 1$.* Since $G$ is connected with $|G| \geq 2$ and every degree at most $1$, $G$ must be $K_2$. But $K_2$ is a complete graph, excluded by hypothesis. So $\Delta(G) \geq 2$. *Case $\Delta(G) = 2$.* Every vertex has degree at most $2$; a connected graph with $\Delta \leq 2$ is either a path $P_k$ (with $k \geq 2$ vertices) or a cycle $C_k$ (with $k \geq 3$ vertices). - If $G = P_k$ with $k \geq 2$, then $\chi(P_k) = 2$ and $\Delta(P_k) \in \{1, 2\}$. For $k = 2$ we have $P_2 = K_2$, already excluded. For $k \geq 3$, $\Delta(P_k) = 2$ and $\chi(P_k) = 2$, so $\chi \leq \Delta$. - If $G = C_k$ with $k \geq 4$ even, $\chi(C_k) = 2 \leq 2 = \Delta(C_k)$. - If $G = C_k$ with $k \geq 3$ odd, $G$ is an odd cycle, excluded by hypothesis. - If $G = C_3 = K_3$, $G$ is a complete graph, excluded by hypothesis. In every remaining sub-case $\chi(G) \leq \Delta(G)$ holds directly. We may therefore assume $\Delta(G) \geq 3$ for the rest of the proof; this in particular forces $|G| \geq 4$. [/step] [step:Set up the strong induction on $|G|$] We prove the following by strong induction on $n := |G|$: *Claim.* For every connected graph $H$ with $|H| = n$, $\Delta(H) \geq 3$, $H$ not a complete graph, and $H$ not an odd cycle, we have $\chi(H) \leq \Delta(H)$. The base case is $n = 4$: the only connected graph on $4$ vertices with $\Delta \geq 3$ is either $K_4$ (excluded) or $K_{1,3}$ (the star, which has $\chi = 2 \leq 3 = \Delta$), $P_4$ or $C_4$ (both have $\Delta = 2$, outside scope), or graphs obtained from $K_4$ by deleting edges. For the star $K_{1,3}$ the claim is direct. For any other connected graph on $4$ vertices with $\Delta = 3$ that is not $K_4$, the three cases below apply with $n = 4$ and the inductive hypothesis is not needed (the arguments are self-contained). *Inductive step.* Fix $n \geq 4$ and suppose the claim holds for all connected graphs $H$ with $|H| < n$ satisfying the other hypotheses. Let $G$ be a connected graph with $|G| = n$, $\Delta(G) \geq 3$, $G \neq K_{\Delta(G)+1}$, and $G$ not an odd cycle. We split on $\kappa(G)$; since $G$ is connected with $n \geq 2$, $\kappa(G) \geq 1$. The three cases $\kappa(G) \geq 3$, $\kappa(G) = 1$, and $\kappa(G) = 2$ are exhaustive. [/step] [step:Assume $\kappa(G) \geq 3$ and find two non-adjacent neighbours of a max-degree vertex] Suppose $\kappa(G) \geq 3$. Let $x_n \in V(G)$ satisfy $\deg_G(x_n) = \Delta(G)$. [claim:Some two vertices of $N(x_n)$ are non-adjacent in $G$] [proof] Suppose for contradiction that every pair of distinct vertices in $N(x_n)$ is adjacent in $G$. Then $G[N(x_n)]$ is a complete graph on $\Delta(G)$ vertices. Since $x_n$ is adjacent to every vertex of $N(x_n)$, the induced subgraph $G[\{x_n\} \cup N(x_n)]$ is complete on $\Delta(G) + 1$ vertices — call this subgraph $K$. We claim $V(G) = V(K)$, so $G = K_{\Delta(G) + 1}$. Suppose for contradiction there is a vertex $w \in V(G) \setminus V(K)$. Since $G$ is connected, there is a path in $G$ from $w$ to $x_n$; let $P = w_0 w_1 \ldots w_r$ be such a path with $w_0 = w$ and $w_r = x_n$. Let $j$ be the largest index with $w_j \notin V(K)$; then $0 \leq j < r$ and $w_{j+1} \in V(K)$ with $w_j w_{j+1} \in E(G)$. Note $w_{j+1} \neq x_n$ (else $w_j \in N(x_n) \subset V(K)$, contradicting $w_j \notin V(K)$), so $w_{j+1} \in N(x_n)$. Now compute $\deg_G(w_{j+1})$. The vertex $w_{j+1} \in N(x_n)$ is adjacent to: - every other vertex of $N(x_n)$: that is $|N(x_n)| - 1 = \Delta(G) - 1$ vertices; - the vertex $x_n$: $1$ more vertex; - the vertex $w_j \notin V(K)$: another $1$ vertex. These are all distinct (the first two lie in $V(K)$, the third does not), so $\deg_G(w_{j+1}) \geq \Delta(G) - 1 + 1 + 1 = \Delta(G) + 1$, contradicting the definition of $\Delta(G)$ as the maximum degree in $G$. Hence $V(G) = V(K)$ and $G = K_{\Delta(G)+1}$, contradicting the hypothesis $G \neq K_{\Delta(G)+1}$. So our initial assumption fails, and there exist non-adjacent $x_1, x_2 \in N(x_n)$. [/proof] [/claim] Fix such $x_1, x_2 \in N(x_n)$ with $x_1 x_2 \notin E(G)$. [/step] [step:Order $V(G)$ via reverse BFS in $G - \{x_1, x_2\}$ rooted at $x_n$] Since $\kappa(G) \geq 3$ and we are removing exactly $2$ vertices, $G - \{x_1, x_2\}$ is connected. Run breadth-first search on $G - \{x_1, x_2\}$ starting at $x_n$. Let $y_1, y_2, \ldots, y_{n-2}$ be the BFS discovery order, so $y_1 = x_n$ and each $y_j$ with $j \geq 2$ has a BFS parent $y_{p(j)}$ with $p(j) < j$ and $y_j y_{p(j)} \in E(G - \{x_1, x_2\}) \subseteq E(G)$. Reverse this order: define $x_{n+1-j} := y_j$ for $j = 1, \ldots, n-2$, so that $x_3, x_4, \ldots, x_{n-1}$ is the reverse of $y_{n-2}, \ldots, y_2$, and $x_n = y_1$. *Parent-later property.* For each $i \in \{3, 4, \ldots, n-1\}$, writing $i = n+1-j$ with $2 \leq j \leq n-2$, the BFS parent $y_{p(j)}$ of $y_j$ satisfies $p(j) < j$, so $n + 1 - p(j) > n + 1 - j = i$, meaning $x_{n+1-p(j)}$ sits *after* $x_i$ in the order $x_3, \ldots, x_n$. And $y_{p(j)} y_j \in E(G)$ translates to $x_{n+1-p(j)} x_i \in E(G)$. Hence every $x_i$ with $3 \leq i \leq n-1$ has at least one neighbour in $\{x_{i+1}, \ldots, x_n\}$. [/step] [step:Greedy-colour in the order $x_1, x_2, x_3, \ldots, x_n$ using $\Delta(G)$ colours] Let $[t] := \{1, 2, \ldots, \Delta(G)\}$ be the palette. Define a colouring $c: V(G) \to [t]$ greedily: process $x_1, x_2, \ldots, x_n$ in order, and at each step assign the smallest colour in $[t]$ not used on any already-coloured neighbour. We verify the algorithm never fails. - *Colour $x_1$.* No predecessors. Set $c(x_1) := 1$. - *Colour $x_2$.* Its only predecessor is $x_1$, but $x_1 x_2 \notin E(G)$ so $x_1$ is not a neighbour. No forbidden colour. Set $c(x_2) := 1$. Note $c(x_1) = c(x_2) = 1$. - *Colour $x_i$ for $3 \leq i \leq n - 1$.* By the parent-later property, $x_i$ has at least one neighbour in $\{x_{i+1}, \ldots, x_n\}$, which has not yet been coloured. So among the at most $\deg_G(x_i) \leq \Delta(G)$ neighbours of $x_i$, at most $\Delta(G) - 1$ precede $x_i$ in the order. Hence at most $\Delta(G) - 1$ colours of $[t]$ are forbidden, and the smallest available colour is well-defined. - *Colour $x_n$.* All $\Delta(G)$ neighbours of $x_n$ precede it in the order (every vertex of $G - x_n$ comes before $x_n$ in our ordering). In particular $x_1, x_2 \in N(x_n)$ both precede $x_n$ and both received colour $1$. So \begin{align*} |\{c(y) : y \in N(x_n)\}| \leq \Delta(G) - 1, \end{align*} because the $\Delta(G)$ neighbours' colours include at most $\Delta(G) - 1$ distinct values (two of them — $x_1$ and $x_2$ — coincide at $1$). Thus at least one colour of $[t]$ is available. The greedy algorithm terminates with a proper colouring $c: V(G) \to [t]$, so $\chi(G) \leq |[t]| = \Delta(G)$. [guided] **Strategy.** We want to $\Delta(G)$-colour $G$ greedily. A naive greedy order could fail at a maximum-degree vertex $v$: if every neighbour of $v$ has a distinct colour, all $\Delta(G)$ colours are used up before $v$, leaving no colour available. The *shared-colour trick* forces two of $v$'s neighbours to receive the same colour, so only $\Delta(G) - 1$ distinct colours are used by the time we reach $v$. **Why $\kappa(G) \geq 3$ is used.** We need to remove $\{x_1, x_2\}$ from $G$ and still have a connected graph, so that a BFS from $x_n$ reaches every remaining vertex. $3$-connectivity guarantees this. **Why we need $x_1 \not\sim x_2$.** The greedy algorithm can give them the same colour only if they are not adjacent — otherwise the proper-colouring condition on the edge $x_1 x_2$ forbids it. Hence the claim that some two neighbours of $x_n$ are non-adjacent is essential; if every pair in $N(x_n)$ were adjacent, the neighbourhood would be a clique and together with $x_n$ would form $K_{\Delta(G)+1}$, which by connectedness and degree-maximality forces $G = K_{\Delta(G)+1}$ (proved above), excluded by hypothesis. **The greedy bound at each vertex.** - At $x_1$: the first vertex — no forbidden colours, pick $1$. - At $x_2$: the only earlier vertex is $x_1$, and $x_1 x_2 \notin E(G)$, so no forbidden colour — pick $1$ again. - At $x_i$ ($3 \leq i \leq n - 1$): the BFS-parent construction guarantees $x_i$ has at least one later neighbour (its BFS parent in the original BFS order, which sits later in the reversed order). So at most $\Delta(G) - 1$ earlier neighbours, at most $\Delta(G) - 1$ forbidden colours, at least one available. - At $x_n$: here is where the trick pays off. All $\Delta(G)$ neighbours of $x_n$ — including $x_1$ and $x_2$ — have been coloured. Since $c(x_1) = c(x_2) = 1$, the $\Delta(G)$ neighbours use at most $\Delta(G) - 1$ colours, leaving at least one colour of $[t]$ free for $x_n$. The greedy colouring succeeds throughout, giving $\chi(G) \leq \Delta(G)$. [/guided] [/step] [step:Assume $\kappa(G) = 1$ and decompose $G$ at a cut vertex] Suppose $\kappa(G) = 1$. Let $z \in V(G)$ be a cut vertex, and let $C_1, C_2, \ldots, C_m$ (with $m \geq 2$) be the vertex sets of the connected components of $G - z$. For each $i \in \{1, \ldots, m\}$, define \begin{align*} G_i := G[C_i \cup \{z\}]. \end{align*} *$G_i$ is connected.* The induced subgraph $G[C_i]$ is connected (as $C_i$ is a component of $G - z$). The vertex $z$ is adjacent in $G$ to at least one vertex of $C_i$, because otherwise $G - C_i$ would have no path from $z$ to $C_i$ and yet $G$ is connected — contradiction. So $G_i = G[C_i] + z + \text{(edges from } z \text{ to } N_G(z) \cap C_i)$ is connected. *$G_i$ is strictly smaller.* $|G_i| = |C_i| + 1$, and since $m \geq 2$ we have $|C_j| \geq 1$ for some $j \neq i$, so $|G_i| = |G| - \sum_{j \neq i} |C_j| \leq |G| - 1 < |G|$. *Degree of $z$ in $G_i$.* In $G_i$, the vertex $z$ is adjacent to $N_G(z) \cap C_i$. Since $z$ has at least one neighbour in every component $C_j$ (by the connectivity argument above) and the components are disjoint, \begin{align*} |N_G(z) \cap C_i| = \deg_G(z) - \sum_{j \neq i} |N_G(z) \cap C_j| \leq \deg_G(z) - (m - 1) \leq \Delta(G) - 1. \end{align*} So $\deg_{G_i}(z) \leq \Delta(G) - 1$. *Colouring each $G_i$.* We produce a proper colouring $c_i: V(G_i) \to [t] = \{1, \ldots, \Delta(G)\}$ by considering two sub-cases. *(a) $G_i = K_{\Delta(G_i) + 1}$.* Every vertex of $G_i$ has degree $\Delta(G_i)$ in $G_i$. In particular $\deg_{G_i}(z) = \Delta(G_i)$, and we showed $\deg_{G_i}(z) \leq \Delta(G) - 1$, so $\Delta(G_i) \leq \Delta(G) - 1$. A complete graph $K_{\Delta(G_i)+1}$ admits the proper colouring that assigns a distinct colour from $\{1, 2, \ldots, \Delta(G_i) + 1\} \subseteq \{1, \ldots, \Delta(G)\} = [t]$ to each vertex — the inclusion holds because $\Delta(G_i) + 1 \leq \Delta(G)$. So a proper $[t]$-colouring of $G_i$ exists directly. *(b) $G_i \neq K_{\Delta(G_i)+1}$.* Also $G_i$ is not an odd cycle: an odd cycle has every vertex of degree exactly $2$, but $\Delta(G_i) \leq \Delta(G)$ and $G_i$ has $\geq 2$ vertices; if $\Delta(G_i) = 2$ then we need $\Delta(G_i) \geq 3$ for the inductive hypothesis, but the fallback is direct. Concretely: if $\Delta(G_i) \leq 2$, then $G_i$ is a path or cycle; paths and even cycles are $2$-colourable hence $\Delta(G)$-colourable (using $\Delta(G) \geq 3 \geq 2$); odd cycles have $\chi = 3 \leq \Delta(G)$, which is at most $\Delta(G)$ since $\Delta(G) \geq 3$. So in all $\Delta(G_i) \leq 2$ sub-sub-cases, $\chi(G_i) \leq 3 \leq \Delta(G)$. If $\Delta(G_i) \geq 3$ and $G_i \neq K_{\Delta(G_i)+1}$ and $G_i$ is not an odd cycle, the inductive hypothesis applies to $G_i$ (it is connected, smaller, and satisfies all conditions), giving $\chi(G_i) \leq \Delta(G_i) \leq \Delta(G)$. In all sub-cases we obtain a proper colouring $c_i: V(G_i) \to [t]$. *Gluing.* For each $i$, the colour $c_i(z) \in [t]$. Let $\pi_i: [t] \to [t]$ be the permutation that swaps $c_i(z)$ with $1$ and fixes all other colours. Then $\pi_i \circ c_i$ is a proper colouring of $G_i$ (composing with any permutation preserves properness) with $(\pi_i \circ c_i)(z) = 1$. Replace $c_i$ by $\pi_i \circ c_i$; now $c_i(z) = 1$ for every $i$. Define $c: V(G) \to [t]$ by $c(v) := c_i(v)$ if $v \in V(G_i)$. *Well-defined.* The only vertex lying in more than one $V(G_i)$ is $z$, which lies in all of them; since $c_i(z) = 1$ for every $i$, all branches agree at $z$. *Proper.* Every edge $uv \in E(G)$ has both endpoints in some single $V(G_i)$ — indeed, if $u, v \in C_j \cup \{z\}$ for some $j$ (which holds because $G - z$'s components partition $V(G) \setminus \{z\}$: if $u, v \in V(G) \setminus \{z\}$ and $uv \in E(G)$, then $u, v$ are in the same component of $G - z$; if $u = z$ or $v = z$, then $uv$ with the non-$z$ endpoint in some $C_j$ is an edge of $G_j$). So $c(u) = c_j(u) \neq c_j(v) = c(v)$ by properness of $c_j$. Hence $\chi(G) \leq \Delta(G)$. [/step] [step:Assume $\kappa(G) = 2$ and decompose $G$ at a $2$-separator] Suppose $\kappa(G) = 2$. Let $S = \{x, y\}$ be a $2$-separator of $G$, and let $C_1, C_2, \ldots, C_k$ (with $k \geq 2$) be the vertex sets of the connected components of $G - S$. For each $i \in \{1, \ldots, k\}$, define \begin{align*} G_i := G[C_i \cup S] + xy, \end{align*} where "$+ xy$" means we add the edge $xy$ if it is not already in $G[C_i \cup S]$. So $xy \in E(G_i)$ for every $i$, regardless of whether $xy \in E(G)$. *$G_i$ is connected.* The induced subgraph $G[C_i]$ is connected (component of $G - S$). Each of $x$ and $y$ has at least one neighbour in $C_i$: if $x$ had no neighbour in $C_i$, then $\{y\}$ alone would separate $C_i$ from $V(G) \setminus (C_i \cup \{y\})$ in $G - x$, meaning $\{y\}$ or $\{x\}$ alone would disconnect $G$, contradicting $\kappa(G) = 2$. (Formally: $\kappa(G) = 2$ means no single vertex disconnects $G$, so both $x$ and $y$ must have neighbours in every $C_i$ for $G$'s connectivity structure to require both.) Thus $G_i$ is connected. *$G_i$ is strictly smaller.* $|G_i| = |C_i| + 2$. Since $k \geq 2$ and each $|C_j| \geq 1$, $|G_i| \leq |G| - 1 < |G|$. We now split on whether $\delta(G_i) < \Delta(G)$ holds for every $i$ (the *generic* sub-case) or $\delta(G_i) = \Delta(G)$ for some $i$ (the *non-generic* sub-case). Note that $\delta(G_i) \leq \deg_{G_i}(z)$ for any vertex $z$; also $\Delta(G_i) \leq \Delta(G)$ cannot be guaranteed because adding the edge $xy$ can raise $\deg(x)$ or $\deg(y)$ in $G_i$ above $\Delta(G)$. We handle degrees carefully in each sub-case. [/step] [step:Handle the generic sub-case $\delta(G_i) < \Delta(G)$ for all $i$] Suppose $\delta(G_i) < \Delta(G)$ for every $i \in \{1, \ldots, k\}$. We produce a proper $\Delta(G)$-colouring of each $G_i$ with $c_i(x) \neq c_i(y)$, then glue. *Colouring $G_i$ with $\Delta(G)$ colours.* Pick any vertex $v_i \in V(G_i)$ with $\deg_{G_i}(v_i) = \delta(G_i) < \Delta(G)$. We colour $G_i$ greedily: perform BFS on $G_i$ from $v_i$, let $z_1 = v_i, z_2, \ldots, z_{|G_i|}$ be the BFS discovery order, and process vertices in reverse order $z_{|G_i|}, z_{|G_i|-1}, \ldots, z_1$. By the same parent-later argument used in Case $\kappa \geq 3$, each $z_j$ for $j \geq 2$ has at least one neighbour in $\{z_{j-1}, z_{j-2}, \ldots, z_1\}$ (its BFS parent), which is coloured *after* $z_j$ in the reverse order. So when we colour $z_j$, at most $\deg_{G_i}(z_j) - 1 \leq \Delta(G_i) - 1$ of its neighbours have been coloured. Now $\Delta(G_i) \leq \max(\Delta(G), \deg_{G_i}(x), \deg_{G_i}(y))$, and $\deg_{G_i}(x) \leq \deg_G(x) + 1 \leq \Delta(G) + 1$ (the $+1$ accounts for the possibly-added edge $xy$); similarly for $y$. So $\Delta(G_i) \leq \Delta(G) + 1$ in the worst case, meaning $\Delta(G_i) - 1 \leq \Delta(G)$ and greedy on $\{z_j : j \geq 2\}$ uses at most $\Delta(G)$ colours. Finally, when we reach $z_1 = v_i$, all its $\delta(G_i) < \Delta(G)$ neighbours have been coloured. So at most $\delta(G_i) \leq \Delta(G) - 1$ colours are forbidden, and at least one colour in $[t] = \{1, \ldots, \Delta(G)\}$ is available. This greedy process produces a proper colouring $c_i : V(G_i) \to [t]$. Since $xy \in E(G_i)$, the colouring is proper on this edge: $c_i(x) \neq c_i(y)$. *Gluing.* For each $i$, the pair $(c_i(x), c_i(y))$ consists of two distinct elements of $[t]$. Choose a permutation $\pi_i: [t] \to [t]$ such that $\pi_i(c_i(x)) = 1$ and $\pi_i(c_i(y)) = 2$. Replace $c_i$ by $\pi_i \circ c_i$; the new $c_i$ is still a proper colouring, and $c_i(x) = 1$, $c_i(y) = 2$ for every $i$. Define $c: V(G) \to [t]$ by $c(v) := c_i(v)$ if $v \in V(G_i)$. *Well-defined.* The only vertices in more than one $V(G_i)$ are $x$ and $y$ (both in every $V(G_i)$); after normalisation, $c_i(x) = 1$ and $c_i(y) = 2$ for every $i$, so all branches agree. *Proper on $G$.* Every edge of $G$ lies in some $G_i$: edges inside a single $C_i$ are in $G_i$; edges from $x$ or $y$ to a vertex of $C_i$ are in $G_i$; the edge $xy$, if in $E(G)$, is in every $G_i$ (with $c(x) = 1 \neq 2 = c(y)$, proper). So $c$ is proper on $G$. Hence $\chi(G) \leq \Delta(G)$. [/step] [step:Handle the non-generic sub-case by switching to a better $2$-separator] Suppose instead that $\delta(G_i) = \Delta(G)$ for some $i$; by relabelling, say $\delta(G_1) = \Delta(G)$. [claim:$\deg_{G_1}(v) = \Delta(G)$ for every $v \in V(G_1)$] [proof] By definition, $\delta(G_1) = \min_v \deg_{G_1}(v) = \Delta(G)$, so $\deg_{G_1}(v) \geq \Delta(G)$ for every $v \in V(G_1)$. For the upper bound: $v \in V(G_1) = C_1 \cup \{x, y\}$. - If $v \in C_1$, then $N_{G_1}(v) = N_G(v) \cap V(G_1)$ (the added edge $xy$ does not touch $v$), so $\deg_{G_1}(v) \leq \deg_G(v) \leq \Delta(G)$. - If $v = x$, then $N_{G_1}(x) = (N_G(x) \cap (C_1 \cup \{y\})) \cup \{y\}$ — in other words, $x$'s neighbours in $G_1$ are $x$'s original neighbours in $C_1 \cup \{y\}$, plus $y$ via the added edge (if $y \notin N_G(x)$). So $\deg_{G_1}(x) \leq |N_G(x) \cap C_1| + 1$ (the $+1$ for $y$, regardless of whether $xy \in E(G)$). - If $v = y$, similarly $\deg_{G_1}(y) \leq |N_G(y) \cap C_1| + 1$. Combining upper and lower: $\deg_{G_1}(v) = \Delta(G)$ for every $v$. [/proof] [/claim] In particular: \begin{align*} |N_{G_1}(x) \cap C_1| &= \deg_{G_1}(x) - |\{y\}| = \Delta(G) - 1, \\ |N_{G_1}(y) \cap C_1| &= \Delta(G) - 1. \end{align*} (Here $|\{y\}| = 1$ accounts for $y \in N_{G_1}(x)$ via the edge $xy \in E(G_1)$.) And the neighbourhood of $x$ in $C_1$ is the same in $G$ and in $G_1$ (adding $xy$ does not affect neighbours inside $C_1$), so $|N_G(x) \cap C_1| = \Delta(G) - 1$ and $|N_G(y) \cap C_1| = \Delta(G) - 1$. [claim:$xy \notin E(G)$, $k = 2$, and each of $x, y$ has exactly one neighbour in $C_2$] [proof] Since $\deg_G(x) \leq \Delta(G)$: \begin{align*} \Delta(G) \geq \deg_G(x) = |N_G(x) \cap C_1| + \sum_{j \geq 2} |N_G(x) \cap C_j| + \mathbb{1}[xy \in E(G)]. \end{align*} Substituting $|N_G(x) \cap C_1| = \Delta(G) - 1$: \begin{align*} \sum_{j \geq 2} |N_G(x) \cap C_j| + \mathbb{1}[xy \in E(G)] \leq 1. \tag{$\ast$} \end{align*} We also have a lower bound. Since $\kappa(G) = 2$, no single vertex disconnects $G$; in particular $\{y\}$ alone does not separate $G$. So in $G - y$, the vertex $x$ is connected to every $C_j$ with $j \geq 2$, which requires that $x$ have at least one neighbour in $\bigcup_{j \geq 2} C_j$ (vertices of $\bigcup_{j \geq 2} C_j$ are not adjacent to $V(G_1) \setminus \{y\}$ in $G - y$ except through $x$). Formally: $G - y$ is connected, and the component structure of $G - y$ must link $C_1$ to each $C_j$ ($j \geq 2$); the only possible links go through $x$ (since $S \setminus \{y\} = \{x\}$). So $x$ has at least one neighbour in each $C_j$ for $j \geq 2$, and in particular \begin{align*} \sum_{j \geq 2} |N_G(x) \cap C_j| \geq k - 1 \geq 1. \tag{$\ast\ast$} \end{align*} Combining ($\ast$) and ($\ast\ast$): \begin{align*} 1 \leq \sum_{j \geq 2} |N_G(x) \cap C_j| \leq 1 - \mathbb{1}[xy \in E(G)]. \end{align*} This forces $\mathbb{1}[xy \in E(G)] = 0$ (i.e., $xy \notin E(G)$) and $\sum_{j \geq 2} |N_G(x) \cap C_j| = 1$. Hence $\sum_{j \geq 2} |N_G(x) \cap C_j| = k - 1 = 1$, so $k = 2$. And $|N_G(x) \cap C_2| = 1$: $x$ has a unique neighbour in $C_2$, call it $x'$. By the identical argument with $y$ in place of $x$: $|N_G(y) \cap C_2| = 1$, and $y$ has a unique neighbour $y' \in C_2$ (possibly $y' = x'$). [/proof] [/claim] We now split on $|C_2|$. *Sub-case $|C_2| = 1$.* In this sub-case $C_2 = \{w_0\}$ for a single vertex $w_0$. Since both $x'$ and $y'$ lie in $C_2$ and are the unique neighbours of $x$ and $y$ there, $x' = y' = w_0$. The degree of $w_0$ in $G$ is $\deg_G(w_0) = |N_G(w_0) \cap (C_1 \cup \{x, y\})| = |\{x, y\}| = 2$ (since $C_1$ and $C_2$ are disjoint components of $G - S$, $w_0$ has no neighbours in $C_1$). We handle this sub-case by direct colouring extension. Consider $G - w_0$. Its vertex set is $C_1 \cup \{x, y\}$, and it inherits exactly the edges of $G[C_1 \cup \{x, y\}]$. We verify $G - w_0$ is connected: $G[C_1]$ is connected (as a component of $G - S$), $x$ has $\Delta(G) - 1 \geq 2$ neighbours in $C_1$, $y$ has $\Delta(G) - 1 \geq 2$ neighbours in $C_1$, so $G - w_0 = G[C_1 \cup \{x, y\}]$ is connected. We produce a proper $\Delta(G)$-colouring of $G - w_0$, splitting on $\Delta(G - w_0)$. Since $\Delta(G - w_0) \leq \Delta(G)$, we have three possibilities. - *If $\Delta(G - w_0) \leq 2$:* The connected graphs with maximum degree at most $2$ are paths and cycles. Paths and even cycles have $\chi \leq 2 \leq \Delta(G)$; odd cycles have $\chi = 3 \leq \Delta(G)$ (using $\Delta(G) \geq 3$). So $\chi(G - w_0) \leq \Delta(G)$. - *If $\Delta(G - w_0) \geq 3$ and $G - w_0$ is not $K_{\Delta(G - w_0)+1}$ and not an odd cycle:* (An odd cycle has $\Delta = 2 < 3$, so this clause automatically holds.) $G - w_0$ is connected, smaller than $G$, and not complete: we verify non-completeness. $x, y \in V(G - w_0)$ and $xy \notin E(G)$ (shown above), so $x, y$ are non-adjacent in $G - w_0$, hence $G - w_0 \neq K_{|G - w_0|}$; and $K_{\Delta(G - w_0)+1}$ on $|G - w_0| \geq \Delta(G - w_0) + 1$ vertices would require all pairs to be adjacent, ruled out by non-adjacent $x, y$. The inductive hypothesis gives $\chi(G - w_0) \leq \Delta(G - w_0) \leq \Delta(G)$. - *If $\Delta(G - w_0) \geq 3$ and $G - w_0 = K_{\Delta(G - w_0)+1}$:* Impossible by the non-adjacent $x, y$ argument above. In all sub-sub-cases we obtain a proper colouring $c': V(G - w_0) \to [t] = \{1, \ldots, \Delta(G)\}$. Extend $c'$ to a colouring $c$ of $G$ by assigning $w_0$ any colour in $[t] \setminus \{c'(x), c'(y)\}$. This set is nonempty: $|\{c'(x), c'(y)\}| \leq 2 \leq \Delta(G) - 1 < \Delta(G) = |[t]|$, using $\Delta(G) \geq 3$. The extension is a proper colouring of $G$ (the only new edges are $w_0 x$ and $w_0 y$, both respected by the choice). Hence $\chi(G) \leq \Delta(G)$, closing the $|C_2| = 1$ sub-case. *Sub-case $|C_2| \geq 2$.* Now $C_2 \setminus \{y'\} \neq \varnothing$. [claim:$\{x, y'\}$ is a $2$-separator of $G$] [proof] Consider $G - \{x, y'\}$. In this graph: - $y$ is adjacent only to $N_G(y) \cap (C_1 \cup C_2) = (N_G(y) \cap C_1) \cup \{y'\}$ in $G$. With $y'$ removed, $y$'s neighbours are $N_G(y) \cap C_1$ — all in $C_1$. - For any $w \in C_2 \setminus \{y'\}$, the neighbours of $w$ in $G - \{x, y'\}$ are $N_G(w) \cap (C_2 \setminus \{y'\})$. In particular $w$ has no neighbour in $C_1 \cup \{y\}$: vertices of $C_2$ are not adjacent to vertices of $C_1$ in $G$ (since $C_1, C_2$ are distinct components of $G - \{x, y\}$), and $|N_G(y) \cap C_2| = 1$ with the unique neighbour being $y'$, so $w \neq y'$ is not adjacent to $y$. Hence in $G - \{x, y'\}$, there is no edge between $C_1 \cup \{y\}$ and $C_2 \setminus \{y'\}$. Both sets are nonempty (the first contains $y$; the second is nonempty since $|C_2| \geq 2$). So $\{x, y'\}$ disconnects $G$. Since $|\{x, y'\}| = 2$ and $\kappa(G) = 2$, $\{x, y'\}$ is a $2$-separator. [/proof] [/claim] *Degree count in the new pieces.* Write $C_2' := C_2 \setminus \{y'\}$ and $D := C_1 \cup \{y\}$. Define the new pieces \begin{align*} G_1' &:= G[D \cup \{x, y'\}] + xy' = G[C_1 \cup \{x, y, y'\}] + xy', \\ G_2' &:= G[C_2' \cup \{x, y'\}] + xy'. \end{align*} (Both pieces include the added edge $xy'$ regardless of whether it is in $E(G)$.) By the same argument as for $G_i$ in the original decomposition, $G_1', G_2'$ are connected and strictly smaller than $G$. [claim:$\delta(G_1') < \Delta(G)$] [proof] Consider the vertex $y' \in V(G_1')$. Its neighbours in $G_1'$ come from: - $N_G(y') \cap V(G_1') = N_G(y') \cap (C_1 \cup \{x, y, y'\}) \setminus \{y'\}$. Now $N_G(y') \subseteq C_2 \cup \{x, y\}$ (since $y' \in C_2$ and $C_1, C_2$ are disjoint components of $G - S$, so $y'$ is not adjacent to any vertex of $C_1$; and $N_G(y') \cap S \subseteq \{x, y\}$). So $N_G(y') \cap V(G_1') \subseteq \{x, y\}$, and specifically equals $\{y\}$ (since $y' \sim y$ by definition of $y'$) plus possibly $\{x\}$ if $xy' \in E(G)$. - Additionally, $y'$ is adjacent to $x$ in $G_1'$ via the added edge $xy'$. So $N_{G_1'}(y') \subseteq \{x, y\}$, hence $\deg_{G_1'}(y') \leq 2$. Since $\Delta(G) \geq 3$, we have $\deg_{G_1'}(y') \leq 2 < \Delta(G)$, so $\delta(G_1') \leq 2 < \Delta(G)$. [/proof] [/claim] [claim:$\delta(G_2') < \Delta(G)$] [proof] Consider the vertex $y'$ in $G_2'$. Its neighbours in $G_2'$ come from: - $N_G(y') \cap V(G_2') = N_G(y') \cap (C_2' \cup \{x, y'\}) \setminus \{y'\} = (N_G(y') \cap C_2') \cup (N_G(y') \cap \{x\})$. Note $y' \sim y$ in $G$ but $y \notin V(G_2')$, so $y$ does not contribute. - The added edge $xy'$: $y'$ gains $x$ as a neighbour. So $N_{G_2'}(y') = (N_G(y') \cap C_2') \cup \{x\}$. Hence \begin{align*} \deg_{G_2'}(y') = |N_G(y') \cap C_2'| + 1 = |N_G(y') \cap (C_2 \setminus \{y'\})| + 1 = |N_G(y') \cap C_2| + 1 \end{align*} (the last equality since $y' \notin N_G(y')$ — a vertex is not its own neighbour). Compute $|N_G(y') \cap C_2|$: the total degree of $y'$ in $G$ is \begin{align*} \deg_G(y') = |N_G(y') \cap C_2| + |N_G(y') \cap \{x, y\}| \leq \Delta(G). \end{align*} We know $y \in N_G(y')$ (so $|N_G(y') \cap \{x, y\}| \geq 1$). Hence $|N_G(y') \cap C_2| \leq \Delta(G) - 1$, and \begin{align*} \deg_{G_2'}(y') = |N_G(y') \cap C_2| + 1 \leq \Delta(G). \end{align*} We need strict inequality. We split on whether $x \in N_G(y')$. - *If $x \in N_G(y')$ (i.e., $xy' \in E(G)$):* Then $|N_G(y') \cap \{x, y\}| = 2$, so $|N_G(y') \cap C_2| \leq \Delta(G) - 2$, giving $\deg_{G_2'}(y') \leq \Delta(G) - 1 < \Delta(G)$. - *If $x \notin N_G(y')$ (i.e., $xy' \notin E(G)$):* Then $|N_G(y') \cap \{x, y\}| = 1$, so $\deg_G(y') = |N_G(y') \cap C_2| + 1$. If $\deg_G(y') = \Delta(G)$, then $|N_G(y') \cap C_2| = \Delta(G) - 1$. But here is the key: we chose $y'$ as the *unique* neighbour of $y$ in $C_2$, with $|N_G(y) \cap C_2| = 1$. Now consider the degree of $y'$ in $G$: $y'$ is adjacent to $y$ and to $\Delta(G) - 1$ vertices of $C_2$. In $G_2'$, $y'$ is adjacent to these $\Delta(G) - 1$ vertices of $C_2 \setminus \{y'\} = C_2'$ plus $x$ (via the added edge), giving $\deg_{G_2'}(y') = \Delta(G)$. So if $\deg_G(y') = \Delta(G)$, then $\deg_{G_2'}(y') = \Delta(G)$, not strict. In the second sub-sub-case we need a different witness. Consider the vertex $x$ in $G_2'$. Its neighbours in $G_2'$ come from: \begin{align*} N_{G_2'}(x) = (N_G(x) \cap C_2') \cup \{y'\}. \end{align*} We know $|N_G(x) \cap C_2| = 1$ (the unique neighbour being $x'$). If $x' \neq y'$, then $x' \in C_2' = C_2 \setminus \{y'\}$, so $|N_G(x) \cap C_2'| = 1$ and $\deg_{G_2'}(x) = 1 + 1 = 2 < \Delta(G)$ (using $\Delta(G) \geq 3$). If $x' = y'$, then $N_G(x) \cap C_2' = \varnothing$, and $\deg_{G_2'}(x) = 0 + 1 = 1 < \Delta(G)$. Either way, $\deg_{G_2'}(x) \leq 2 < \Delta(G)$, so $\delta(G_2') \leq 2 < \Delta(G)$. In all sub-sub-cases $\delta(G_2') < \Delta(G)$. [/proof] [/claim] *Applying the generic sub-case to $\{x, y'\}$.* Both $G_1'$ and $G_2'$ have $\delta < \Delta(G)$, so the generic sub-case's argument — with $\{x, y'\}$ playing the role of $\{x, y\}$ and $G_1', G_2'$ the pieces — produces a proper $\Delta(G)$-colouring of $G$. Explicitly: colour each $G_i'$ greedily from its minimum-degree vertex (starting the BFS there and reversing) using at most $\Delta(G)$ colours; the added edge $xy' \in E(G_i')$ forces $c_i(x) \neq c_i(y')$; permute palettes so all $c_i$ agree on $(x, y')$; glue. Hence $\chi(G) \leq \Delta(G)$. [guided] **Why saturation is a problem.** The $2$-separator $\{x, y\}$ decomposes $G$ into pieces $G_1, \ldots, G_k$ (with the edge $xy$ added to each). The generic sub-case relies on each piece having a vertex of degree $< \Delta(G)$ — because our greedy colouring starts at such a vertex and uses it as the "saving vertex" when we finish the BFS traversal. If some piece $G_1$ has $\delta(G_1) = \Delta(G)$, every vertex there has full degree, so no saving vertex exists — we cannot directly colour $G_1$ with $\Delta(G)$ colours this way. **Saturation forces regularity.** From $\delta(G_1) = \Delta(G)$, every vertex $v$ of $G_1$ satisfies $\deg_{G_1}(v) \geq \Delta(G)$. We show equality. For $v \in C_1$, the added edge $xy$ does not touch $v$, so $\deg_{G_1}(v) = \deg_G(v) \leq \Delta(G)$. For $v = x$, the neighbours of $x$ in $G_1$ are those in $C_1$ plus $y$ (via the added edge $xy \in E(G_1)$), so $\deg_{G_1}(x) = |N_G(x) \cap C_1| + 1 \leq \deg_G(x) + 1 \leq \Delta(G) + 1$; but combined with the equality $\deg_{G_1}(x) = \Delta(G)$ forced by saturation, we conclude $|N_G(x) \cap C_1| = \Delta(G) - 1$. Symmetrically for $y$. **Counting across the cut.** Now we count $\deg_G(x)$: \begin{align*} \deg_G(x) = \underbrace{|N_G(x) \cap C_1|}_{= \Delta(G) - 1} + \sum_{j \geq 2} |N_G(x) \cap C_j| + \mathbb{1}[xy \in E(G)] \leq \Delta(G). \end{align*} So $\sum_{j \geq 2} |N_G(x) \cap C_j| + \mathbb{1}[xy \in E(G)] \leq 1$. Connectedness of $G$ demands $x$ have at least one neighbour on the "other side" of the cut (else $\{y\}$ alone would separate $G$, contradicting $\kappa(G) = 2$), so $\sum_{j \geq 2} |N_G(x) \cap C_j| \geq 1$. **Ruling out $xy \in E(G)$ and forcing $k = 2$.** From the two bounds, $\sum_{j \geq 2} |N_G(x) \cap C_j| = 1$ and $xy \notin E(G)$ (if it were, the sum would be $\leq 0$, impossible). Similarly $\sum_{j \geq 2} |N_G(y) \cap C_j| = 1$. Since each $C_j$ (for $j \geq 2$) needs at least one neighbour of $x$ in it (else $\{y\}$ would separate $C_j$ from $C_1$), and the total count is $1$, there is exactly $k - 1 = 1$ such component, giving $k = 2$. **The unique neighbours $x', y' \in C_2$.** Each of $x$ and $y$ has exactly one neighbour in $C_2$ — call these $x'$ and $y'$ (possibly equal). **Why is $\{x, y'\}$ a better separator?** Removing $\{x, y'\}$ from $G$: $y$ loses its link to $C_2$ (because $y$'s only neighbour in $C_2$ was $y'$), so $\{C_1 \cup \{y\}\}$ is disconnected from $C_2 \setminus \{y'\}$ in the remaining graph. Both sides are nonempty (assuming $|C_2| \geq 2$, the small case $|C_2| = 1$ handled separately above). So $\{x, y'\}$ is a $2$-separator. **Why the new pieces satisfy $\delta < \Delta(G)$.** In the new piece $G_1' = G[C_1 \cup \{y, x, y'\}] + xy'$, the vertex $y'$ has at most $2$ neighbours: $y$ (its only neighbour in $C_1 \cup \{y\}$ since $y' \in C_2$ is not adjacent to $C_1$, and $y$ is the unique neighbour of $y'$ in $S$ up to the possibly-also $x$), and $x$ (via the added edge). So $\deg_{G_1'}(y') \leq 2 < \Delta(G)$, giving $\delta(G_1') < \Delta(G)$. For the other piece $G_2'$, the argument splits on whether $xy' \in E(G)$: - If yes, $y'$'s degree drops because one of its "other-side" neighbours is duplicated by the added edge. - If no, consider $x$ instead: $x$'s neighbours in $G_2'$ are $(N_G(x) \cap C_2') \cup \{y'\}$, and $|N_G(x) \cap C_2| = 1$, so $\deg_{G_2'}(x) \leq 2 < \Delta(G)$. Either way, $\delta(G_2') < \Delta(G)$. **Closing.** The generic sub-case now applies to $\{x, y'\}$ (in place of $\{x, y\}$), giving $\chi(G) \leq \Delta(G)$. **The small case $|C_2| = 1$.** If $|C_2| = 1$, then $C_2 = \{w_0\}$ with $w_0 = x' = y'$ (the unique common neighbour of $x$ and $y$ in $C_2$) and $\deg_G(w_0) = 2$. We handle this directly: colour $G - w_0$ first, then extend. Since $xy \notin E(G)$, the vertices $x, y$ are non-adjacent in $G - w_0$, so $G - w_0$ is not a complete graph; if $\Delta(G - w_0) \geq 3$, the inductive hypothesis applies to give $\chi(G - w_0) \leq \Delta(G)$, and if $\Delta(G - w_0) \leq 2$ then $G - w_0$ is a path or cycle with $\chi \leq 3 \leq \Delta(G)$. Now extend by giving $w_0$ any colour in $[t] \setminus \{c(x), c(y)\}$ — a nonempty set of size $\geq \Delta(G) - 2 \geq 1$. [/guided] [/step] [step:Combine the three cases] The cases $\kappa(G) \geq 3$, $\kappa(G) = 1$, and $\kappa(G) = 2$ are exhaustive and mutually exclusive. In each, we constructed a proper colouring $c: V(G) \to \{1, \ldots, \Delta(G)\}$. Hence $\chi(G) \leq \Delta(G)$, completing the inductive step. By strong induction, $\chi(G) \leq \Delta(G)$ for every connected graph $G$ with $|G| \geq 2$, $\Delta(G) \geq 3$, $G \neq K_{\Delta(G)+1}$, and $G$ not an odd cycle. Combined with the direct low-$\Delta$ analysis at the start, the theorem holds in full generality: every connected graph that is neither a complete graph nor an odd cycle satisfies $\chi(G) \leq \Delta(G)$. [/step]