Brooks 定理

更深一层看，困难并不来自高最大度本身，而来自能否安排一种着色次序，使每个待染顶点在轮到它时至少少见一种邻色。完全图把所有颜色两两强制分开，奇环则用奇偶性堵死二染色；它们恰好是这种“腾出一色”策略无法奏效的连通结构。证明中的生成树次序或双连通分解，都是在寻找一个不会同时看见全部 $\mathrm{\Delta }$ 种颜色的最后阶段。

连通立方图若不是 $K_4$，其色数至多三。偶圈满足 $\chi =2=\mathrm{\Delta }$；奇圈是明确例外。$K_2$ 也是完全图例外，尽管其色数二、最大度一。连通性只为简洁表述；不连通图若某分量是完全图或奇圈，仍可能达到 $\mathrm{\Delta }+1$。定理要求简单图；环会使正常着色不可能，多重边虽不改变顶点着色约束但改变度数。Brooks 给出上界，不保证 $\chi (G)=\mathrm{\Delta }$，树通常只需两色而最大度可很大。

以三维立方体图为例，每个顶点度数为 $3$，但按二分图的两侧染色只需两色，说明定理给出的 $\chi (G)\le 3$ 可以远非等号。另一方面，$K_4$ 的四个顶点两两相邻，确实需要四种颜色而 $\mathrm{\Delta }=3$；五边形 $C_5$ 需要三色而 $\mathrm{\Delta }=2$。这两个计算直接展示为什么例外项不能删去。

它把图染色公理库图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。的一般贪心上界从 $\mathrm{\Delta }+1$ 推进到结构性界 $\mathrm{\Delta }$，并说明达到最坏界的障碍可由完全图公理库完全图Complete graph每一对不同顶点都恰有一条边相连的有限简单无向图。与奇圈公理库路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。精确描述。结合连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。和块分解，可先逐分量、再逐双连通块组织着色；在算法上，这也给出线性时间构造 Brooks 着色的路线，而不仅是存在性结论。