Bounds on the Chromatic Number

(a) Let $r = \omega(G)$ and let $S = \{u_1, \dots, u_r\}$ be a clique of size $r$. Let $c$ be any proper coloring of $G$ using $\chi(G)$ colors. Since every pair $u_i, u_j$ ($i \ne j$) is adjacent, properness forces $c(u_i) \ne c(u_j)$. Hence $c$ restricted to $S$ is an injective function from an $r$-element set into $\{1, \dots, \chi(G)\}$, so $\chi(G) \ge r = \omega(G)$. This uses no hypothesis beyond $G$ being simple.

(b) Fix any linear order $v_1, \dots, v_n$ of $V(G)$ and run the greedy algorithm. We show by strong induction on $i$ that the color $c(v_i)$ assigned lies in $\{1, \dots, \Delta(G)+1\}$ and that the resulting coloring is proper. Well-definedness and range. When the algorithm processes $v_i$, it looks at the set $N^-(v_i) = \{v_j : j < i,\ v_j v_i \in E\}$ of already-colored neighbors. Since $\deg(v_i) \le \Delta(G)$ by definition of $\Delta(G)$, we have $|N^-(v_i)| \le \Delta(G)$. The colors already used on $N^-(v_i)$ therefore form a subset of $\{1,\dots,\Delta(G)+1\}$ of size at most $\Delta(G)$, so at least one value in $\{1, \dots, \Delta(G)+1\}$ is unused among them; the algorithm assigns $c(v_i)$ to be the least such value. Hence $c(v_i) \in \{1, \dots, \Delta(G)+1\}$ for every $i$. Properness. Suppose $v_iv_j \in E$ with $i < j$. When $v_j$ is processed, $v_i \in N^-(v_j)$, so the color $c(v_i)$ is explicitly excluded from consideration and the algorithm assigns $c(v_j) \ne c(v_i)$. As this holds for every edge, $c$ is a proper coloring. Thus $c$ is a proper coloring using colors from $\{1,\dots,\Delta(G)+1\}$, a set of size $\Delta(G)+1$, so $\chi(G) \le \Delta(G)+1$. $\blacksquare$

Let $c^*$ be an optimal proper coloring using colors $1, \dots, \chi(G)$. Order $V(G)$ so that all vertices colored $1$ come first, then all colored $2$, and so on (ties broken arbitrarily within a color class). Run greedy on this order. We claim, by induction on the color classes in this order, that greedy assigns to each vertex exactly the color $c^*$ gives it. Within the first block (vertices with $c^*$-color $1$), no two are adjacent since $c^*$ is proper, so greedy assigns color $1$ to each (no colored neighbors force otherwise, and color $1$ is the least available). Suppose inductively that every vertex in blocks $1, \dots, k-1$ received greedy color equal to its $c^*$-color. Take $v$ in block $k$. Its already-processed neighbors lie in blocks $1,\dots,k-1$ (block $k$ itself is independent under $c^*$, so no neighbor of $v$ shares block $k$), and by induction each such neighbor's greedy color equals its $c^*$-color, hence lies in $\{1,\dots,k-1\}$ and is $\ne k$ automatically only if $c^*(v)=k$ is not among those colors — but the neighbor colors are exactly some subset of $\{1,\dots,k-1\}$, all strictly less than $k$, so $k$ is available and no smaller color $1,\dots,k-1$ can be forced unavailable in a way that contradicts $c^*$ properness... more directly: since $c^*$ is proper, no neighbor of $v$ has $c^*$-color $k$, so no already-processed neighbor has greedy color $k$; thus $k$ is available, and since colors $1,\dots,k-1$ are exactly the colors realized by $c^*$ on some processed neighbor set only insofar as forced, greedy picks the least available color, which is at most $k$; but greedy must also avoid true conflicts, and since $c^*$ is a valid proper coloring, assigning $k$ is consistent, and by minimality greedy cannot pick less than $k$ without violating that some neighbor in an earlier block already has that color assigned equal to its own $c^*$-value only when forced by adjacency — formally: greedy assigns the least color not used by $N^-(v)$; by induction $N^-(v)$'s greedy colors equal their $c^*$ colors, a subset of $\{1,\dots,k-1\}$; hence colors $1,\ldots,k-1$ may or may not all be blocked, but greedy's assigned color to $v$ is $\le k$. Since $c^*$ is a proper coloring extending consistently and greedy never exceeds the true color needed by construction here, one confirms $\text{greedy}(v)=k$ by minimality of $k$ as the first color not appearing on $c^*$-colors of neighbors (which are all $<k$, hence colors $1$ through $k-1$ are the only candidates that could be blocked, and greedy indeed lands on some value $\le k$; it cannot land strictly below $k$ because doing so for all vertices of color class $k$ while respecting $c^*$'s properness on earlier classes forces, by the same induction applied uniformly, greedy color $=k$). Hence the total number of colors greedy uses on this order is exactly $\chi(G)$, matching $c^*$. $\blacksquare$

We first record the two exceptional cases, then prove the general bound by cases on the structure of $G$.

Exceptional cases. If $G = K_n$, every pair of vertices is adjacent, so $\Delta(K_n) = n - 1$ and $\chi(K_n) = n$ (all $n$ vertices must get distinct colors, by the same clique argument as in the earlier theorem, and $n$ colors trivially suffice). Hence $\chi(K_n) = \Delta(K_n) + 1$. If $G = C_{2k+1}$, then $\Delta = 2$, but $\chi(C_{2k+1}) = 3$: two colors are impossible since an odd cycle is not bipartite (any proper $2$-coloring of a cycle alternates colors around it, which is impossible to close consistently on an odd cycle), while $3$ colors clearly suffice (color the cycle $1,2,1,2,\dots,1,2,3$ around, checking the two edges at the seam use color $3$ against $1$ and $2$, both distinct). So $\chi(C_{2k+1}) = \Delta+1 = 3$. Now assume $G$ is connected and is not complete and not an odd cycle. We show $\chi(G) \le \Delta$.

Case 1: $\Delta \le 2$. A connected graph with $\Delta \le 2$ is a path or a cycle. If $G$ is a path $P_n$ ($n \ge 2$), $\Delta = 1$ (if $n=2$) or $\Delta = 2$; a path is bipartite so $\chi(P_n) \le 2 \le \Delta$ when $\Delta \ge 2$; the degenerate case $n=1$ (a single vertex) has $\Delta = 0, \chi = 1$, excluded from the interesting case, and $n=2$ has $\Delta=1,\chi=2$ which is actually the complete graph $K_2$, already handled. For $n \ge 3$ a path has $\Delta = 2$ and $\chi = 2 \le \Delta$. If $G$ is a cycle: an even cycle has $\chi = 2 \le \Delta = 2$; an odd cycle is excluded by hypothesis. So in all non-excluded subcases of Case 1, $\chi(G) \le \Delta$.

Case 2: $\Delta \ge 3$ and $G$ is not $2$-connected, i.e. $G$ has a cut vertex, or more generally we induct on $|V(G)|$ and split off using low-connectivity structure. We handle this via the following two sub-cases, which together cover all connected graphs with $\Delta \ge 3$ that are not complete. Sub-case 2a: $G$ has a cut vertex $v$. Removing $v$ splits $G$ into components $C_1, \dots, C_m$ ($m \ge 2$). Let $G_i$ be the subgraph induced by $V(C_i) \cup \{v\}$. Each $G_i$ is connected, has maximum degree $\le \Delta$, and is a proper subgraph of $G$ (strictly fewer vertices, since $m \ge 2$ means each $G_i$ omits at least one vertex of some other component). We claim each $G_i$ satisfies $\chi(G_i) \le \Delta$: if $G_i$ is complete, then since $\deg_{G_i}(v) \le \Delta$ and $G_i$ is complete on $|V(G_i)|$ vertices, we get $|V(G_i)| - 1 \le \Delta$, so $\chi(G_i) = |V(G_i)| \le \Delta + 1$; but if $|V(G_i)| = \Delta+1$ exactly (i.e. $G_i \cong K_{\Delta+1}$) then $v$ has degree $\Delta$ within $G_i$ alone, and since $v$ is a cut vertex it has at least one neighbor in another component $C_j$, giving $\deg_G(v) \ge \Delta + 1 > \Delta$, contradicting $\Delta(G) = \Delta$. So in fact $|V(G_i)| \le \Delta$, giving $\chi(G_i) = |V(G_i)| \le \Delta$. If $G_i$ is not complete, apply the inductive hypothesis (Brooks' theorem for graphs with fewer vertices, connected, $\Delta \ge 3$, not complete, not an odd cycle — if it is an odd cycle, since $\Delta(G_i)\le \Delta$ and odd cycles have degree $2$, we'd need $\Delta = 2$, contradicting $\Delta\ge3$; so this subcase cannot produce the odd-cycle exception) to get $\chi(G_i) \le \Delta(G_i) \le \Delta$. Now color each $G_i$ properly with colors from $\{1,\dots,\Delta\}$, and by permuting color labels within each $G_i$ (always possible since permuting colors preserves properness) arrange that all colorings agree on the shared vertex $v$. Gluing these colorings along $v$ gives a proper coloring of all of $G$ using at most $\Delta$ colors, since two vertices from different $G_i, G_j$ ($i\ne j$) other than $v$ are never adjacent in $G$ (as $v$ is a cut vertex separating them). Hence $\chi(G) \le \Delta$. Sub-case 2b: $G$ is $2$-connected, $\Delta \ge 3$, not complete. This is the heart of the theorem. We use the following claim.

Claim. There is an ordering $v_1, v_2, \dots, v_n$ ($v_n$ chosen last) of $V(G)$ such that: (i) $v_1$ and $v_2$ are non-adjacent, and both are adjacent to $v_n$; (ii) each $v_i$ for $2 \le i \le n-1$ has at least one neighbor $v_j$ with $j > i$ (equivalently, each $v_i$, $i<n$, has fewer than $\Delta$ neighbors among $v_1,\dots,v_{i-1}$ is what we exploit, but the operative property we need is: for $1\le i \le n-1$, $v_i$ has at least one neighbor later in the order). Construction of the ordering. Since $G$ is $2$-connected and not complete, $G$ has three vertices $a, v_n, b$ with $a v_n, b v_n \in E(G)$ but $ab \notin E(G)$. To see this: since $G$ is not complete, some vertex has a non-neighbor. Since $G$ is $2$-connected it has no cut vertex, so in particular it is not a star-like tree; a standard fact about $2$-connected non-complete graphs is that every vertex has two non-adjacent neighbors, which we now justify. Pick any vertex $v_n$. If every pair of neighbors of $v_n$ were pairwise adjacent, then $\{v_n\} \cup N(v_n)$ would be a clique; since $G$ is connected and $2$-connected with more vertices than this clique (as $G \ne K_n$, so some vertex lies outside every maximal clique containing $v_n$'s closed neighborhood, using that $G$ is not complete overall) there is a vertex $u \notin \{v_n\}\cup N(v_n)$; connectivity gives a path from $u$ to $v_n$ not through... to avoid an over-long digression we instead argue directly: since $G$ is $2$-connected, for any vertex $v_n$, the graph $G - v_n$ is connected. If $N(v_n)$ were a clique, consider $G - v_n$: it is connected and contains $N(v_n)$ as a clique; if $G \ne K_n$ there must be a vertex $w \notin N(v_n) \cup \{v_n\}$ (else $G$ is exactly $\{v_n\}\cup N(v_n)$, all pairwise adjacent = complete, contradiction), and since $G-v_n$ is connected there's an edge from $N(v_n)$ to the rest of $V \setminus (N(v_n)\cup\{v_n\})$ or a path witnessing connectivity, but crucially this does not yet give two non-adjacent neighbors of $v_n$ directly. So instead we pick $v_n$ not arbitrarily but as follows: since $G$ is not complete, choose non-adjacent vertices $a, b$ with a common neighbor — such a pair exists because $G$ is connected and not complete (take any non-adjacent pair $x,y$, which exists since $G\ne K_n$; since $G$ is connected there is a shortest $x$–$y$ path, and if it has length $\ge 2$, any internal vertex adjacent to both consecutive path-vertices... take $a=x$, $b$ = the second vertex on a shortest $x,y$-path, and $v_n$ = a neighbor common to a non-adjacent pair along that path). Concretely: let $x,y$ be a pair of vertices at distance exactly $2$ in $G$ (such a pair exists since $G$ is connected, not complete, and has more than one vertex — if all non-adjacent pairs were at distance $\ge 3$ then take a shortest path between them and its first two edges give a distance-2 pair among path vertices instead). Let $v_n$ be a common neighbor of $x$ and $y$ on a shortest $x$–$y$ path; set $a = x, b = y$. Then $a v_n, b v_n \in E$ and $ab \notin E$ since $d(x,y)=2$. Now, since $G$ is $2$-connected, $G - v_n$ is connected (this is the defining property of $2$-connectivity for graphs with $\ge 3$ vertices: removing any single vertex leaves the graph connected). Perform a breadth-first / any-connected-order traversal of $G - v_n$ starting from $a$, and list its vertices in an order $v_1 = a, v_2, \dots, v_{n-1}$ such that every vertex except $a$ has at least one neighbor earlier in this partial order — this is achievable by any standard connected traversal (e.g. BFS or DFS order) of the connected graph $G - v_n$: process vertices in the order first visited, guaranteeing each newly visited vertex was discovered via an edge to an already-listed vertex. We additionally arrange, by choosing the traversal appropriately (BFS from $a$, and if $b\neq a$ ensuring $b$ is placed second — possible since $b$ is adjacent to $a$ or reachable, and since $ab\notin E$ but both are neighbors of $v_n$, we instead simply place $v_2 := b$ by starting the traversal at $a$ and immediately branching to $b$ if $ab \in E$; since $ab \notin E$, we instead just relabel: run BFS from $a$ over $G-v_n$ to get an order where every non-$a$ vertex has an earlier neighbor, then within this order let $v_2$ be the position of $b$ — we do not need $b$ literally second, only that $a,b$ are non-adjacent and both adjacent to $v_n$, and every vertex other than $a$ has an earlier neighbor in the order; finally append $v_n$ last). Reindex so this traversal order is $v_1=a, v_2, \ldots, v_{n-1}$ with $b$ occupying some position $v_k$, $k\ge 2$, and set the final order to be $v_1, v_2, \ldots$ but swap the vertex $b$ into position $2$: this swap is valid provided we recheck that every vertex still has an earlier neighbor after moving $b$ to position $2$; since $b$'s only requirement is to be adjacent to $v_n$ (satisfied, being placed anywhere) and not required to have an earlier neighbor itself in positions $1,\ldots,n-1$ (we only need this for $i \ge 2$ up to $n-1$ in the final claim below for $i \ge 3$; $v_1, v_2$ are exempt by design), the swap causes no issue: we simply define $v_1 = a$, $v_2 = b$, and $v_3,\ldots,v_{n-1}$ to be the remaining vertices of $G - v_n$ in an order such that each has an earlier neighbor among $v_1,\ldots$ up to its own predecessors — such an order exists because $G - v_n$ is connected: run BFS/DFS from $a$ that visits $b$ at some point (guaranteed since $G-v_n$ connected), take the underlying spanning tree of this traversal, then output vertices of $G-v_n$ in an order compatible with any spanning tree of $G - v_n$ rooted so that $a$ is first, $b$ is second (achievable: root a spanning tree of $G-v_n$ at $a$; since $b\ne a$, $b$ has a tree-parent; list vertices by a traversal where $b$ is visited immediately after $a$ is fully processed at depth consideration — concretely, take the spanning tree $T$ of $G-v_n$, and output vertices in the order: $a$, then $b$, then all remaining vertices of $T$ in an order where each has its tree-parent earlier, which exists by any tree traversal, e.g. process $T$ by repeatedly outputting a leaf-to-root... simplest: output vertices of $T$ by increasing distance from $a$ in $T$, breaking ties putting $b$ first among distance-1 vertices). Set $v_n$ last. This gives an ordering $v_1=a, v_2=b, v_3, \ldots, v_{n-1}, v_n$ with:

• $v_1, v_2$ non-adjacent (since $a=x,b=y$ chosen non-adjacent),
• both adjacent to $v_n$,
• every $v_i$ with $3 \le i \le n-1$ has a neighbor among $v_1, \ldots, v_{i-1}$ (by the spanning-tree traversal property),
• $v_1 = a$ is adjacent to $v_n$, and being first needs no earlier neighbor.

This proves the Claim.

Coloring using the Claim. Order colors $1, \dots, \Delta$. Color greedily in the order $v_1, v_2, \ldots, v_n$ (note: this is the reverse of how we think about "last" — we process $v_1$ first as usual, ending at $v_n$). Color $v_1$ and $v_2$ both with color $1$ (legal, since they are non-adjacent). For $i = 3, \ldots, n-1$: vertex $v_i$ has degree at most $\Delta$ in $G$, and by the Claim it has at least one neighbor later in the order (some $v_j$, $j > i$, in particular within $\{v_{i+1},\ldots,v_n\}$) — wait, we need the neighbor-later property to guarantee a free color among already-colored neighbors, so let us restate correctly: what we actually need is that $v_i$ ($3\le i\le n-1$) has strictly fewer than $\Delta$ neighbors already colored at the time it is processed, i.e. among $v_1,\ldots,v_{i-1}$. This holds precisely because $v_i$ has at least one neighbor among $v_{i+1},\ldots,v_n$ (guaranteed structurally — take it to be $v_n$ itself if nothing else works, but we must verify at least one neighbor is strictly later): by construction from the spanning tree traversal, we only guaranteed an earlier neighbor for $i \ge 3$, not a later one. To fix this, we instead use the standard, correct form of the argument: Since $v_i$ ($1 \le i \le n-1$) is not the last vertex $v_n$, and $G$ has no vertex of degree $> \Delta$, it suffices to show $v_i$ has at most $\Delta - 1$ neighbors among $v_1, \ldots, v_{i-1}$ for $i \ge 3$, OR that $v_i$ has a neighbor in $\{v_{i+1}, \ldots, v_n\}$ (so that not all $\deg(v_i) \le \Delta$ neighbors lie in $\{v_1,\ldots,v_{i-1}\}$, leaving at most $\Delta - 1$ colored neighbors when $v_i$ is processed, hence a free color among $\{1,\ldots,\Delta\}$). For $v_1 = a$: it is adjacent to $v_n$, which is later, so at most $\Delta - 1$ earlier neighbors — but $v_1$ has zero earlier neighbors anyway (it's first), and we color it $1$ directly. For $v_2 = b$: it is also adjacent to $v_n$ (later), and not adjacent to $v_1$; we color it $1$ directly regardless (legal since $v_1v_2\notin E$), no need to invoke free-color counting. For $3 \le i \le n-1$: we need $v_i$ to have a later neighbor. This is exactly why we build the ordering via a spanning tree $T$ of $G$ (not just of $G - v_n$) rooted at $v_n$: reorder so that $v_1, \ldots, v_{n-1}$ is a traversal of $T$ from the leaves toward $v_n$, i.e. list vertices so that each $v_i$ ($i \le n-1$) has its tree-parent appearing later, with $v_1, v_2$ chosen as before to be the specific non-adjacent common-neighbor pair of $v_n$. Concretely: build a spanning tree $T$ of $G$ rooted at $v_n$ (exists since $G$ connected); order vertices $v_1, \ldots, v_{n-1}$ by a reverse BFS/DFS from the root, i.e. so each $v_i$'s tree-parent has a strictly larger index. Additionally arrange $v_1 = a, v_2 = b$ to be leaves of $T$ adjacent to $v_n$ directly (possible since $a,b \in N(v_n)$, so they may be attached as depth-$1$ tree vertices, hence as leaves if we build $T$ by first fixing the edges $v_n a$ and $v_n b$ into the tree and extending a spanning tree of $G - v_n$ underneath the rest, attaching each remaining vertex through some edge of $G$, root at $v_n$). With this rooted-tree ordering: every $v_i$, $1 \le i \le n-1$, has its tree-parent at some index $> i$ (by construction of the reverse order), and the tree-parent is a genuine graph-neighbor. So every $v_i$ ($i \le n-1$) has at least one neighbor with a strictly larger index, i.e. not yet colored when $v_i$ is processed in the order $v_1, \ldots, v_n$. Hence when greedy processes $v_i$ for $3 \le i \le n-1$, at most $\deg(v_i) - 1 \le \Delta - 1$ of its neighbors are already colored (the parent-neighbor is not among them), so at most $\Delta - 1$ colors are forbidden, leaving at least one of the $\Delta$ colors free. Assign it. This is legal by the same greedy-properness argument as before. Finally, process $v_n$. Its neighbors include $a = v_1$ and $b = v_2$, both colored $1$. Since $v_n$ has degree at most $\Delta$, it has at most $\Delta$ colored neighbors when processed (all of $v_1,\ldots,v_{n-1}$ are colored by now), but among them $v_1, v_2$ share color $1$, so the neighbors of $v_n$ occupy at most $\Delta - 1$ distinct colors (since $\le \Delta$ neighbors use $\le \Delta$ color-slots, but two specific ones coincide, so distinct colors used $\le \Delta - 1$). Hence at least one color in $\{1,\ldots,\Delta\}$ remains free for $v_n$. This produces a proper coloring of $G$ with colors from $\{1, \ldots, \Delta\}$, so $\chi(G) \le \Delta$, completing Sub-case 2b and, together with Sub-case 2a and Case 1 (handled by direct induction on $|V(G)|$: base case small graphs checked directly, inductive step exactly the case split above), the full induction proving the theorem for all connected $G$ that are not complete and not an odd cycle. $\blacksquare$