Brooks 定理

任意次序的贪心着色只保证当前顶点至多看见 $\mathrm{\Delta }$ 种邻色，因此预备 $\mathrm{\Delta }+1$ 色一定够用。要减少一色，就得安排次序，确保当前顶点的已染邻点至多使用 $\mathrm{\Delta }-1$ 种颜色。

这个目标有两种实现方式：留下一个尚未染色的邻点，或让两个已染邻点共用一种颜色。完全图禁止后一种安排；奇圈在最大度二时则受到奇偶性阻碍。定理的难点是证明除此之外，总能组织好顶点顺序及必要的分块拼接。

一段可直接验证的证明 ​

先处理非正则图。选一个度数小于 $\mathrm{\Delta }$ 的顶点 $r$，取以 $r$ 为根的生成树理路生成树Spanning tree包含原图全部顶点且自身为树的子图。，按子节点先于父节点的顺序染色。每个非根顶点轮到时，父节点尚未染色，所以至多有 $\mathrm{\Delta }-1$ 个已染邻点；最后的根本来就只有至多 $\mathrm{\Delta }-1$ 个邻点。于是这一路径完整地构造了 $\mathrm{\Delta }$ 色着色。

若图正则且有割点，可把各分量连同割点分别着色，再置换颜色名称使割点颜色一致。余下正则且双连通的情形需要更强的结构论证。典型构造找到互不相邻、具有公共邻点 $r$ 的两个顶点 $u,v$，且删去它们后图仍连通；先令 $u,v$ 同色，再沿剩余图的生成树向根 $r$ 染色。最后 $r$ 的两个邻点同色，仍有一种颜色可用。选出适当顶点或处理分离情形，是完整证明中不可省略的部分；任取两个不相邻顶点并不保证这一条件。

连通三正则图若不是 $K_4$，色数至多三。三维立方体图的顶点可标为三个二进制位，两个顶点在恰好一位不同时相邻；按位和的奇偶性分成两色，立即得到 $\chi =2<3=\mathrm{\Delta }$。所以 Brooks 给的是上界，不承诺等号。

偶圈交替用两色即可，满足 $\chi =\mathrm{\Delta }=2$。五边形 $C_5$ 交替染色会在首尾发生冲突，故需要三色；$K_4$ 则需要四色而最大度为三。这两个例子说明定理中的两类例外都不能删除。非平凡树也只有两色，而星形树的最大度可以任意大，界可能很松。

不连通图的色数是各分量色数的最大值，应逐分量使用定理。出现例外分量并不自动使整体达到 $\mathrm{\Delta }(G)+1$：例如一个三角形与一棵最大度四的星形树的不交并，整体色数为三、最大度为四。只有例外分量本身的最大度达到全图最大度，才会迫使这一最坏值。

这里讨论的是简单图的正常顶点着色。自环要求一个顶点与自身异色，使正常着色不存在；平行边不增加顶点异色约束，却改变按重数计的度数，因而不能不加说明地套用同一“例外恰好如此”的表述。

Brooks 定理为图染色理路图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。提供结构性保证：完全图和奇圈理路路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。解释了贪心上界的全部连通极端情形。它并不提供一般图色数的精确求解方法，也不能凭 $\chi \le \mathrm{\Delta }$ 判定是否还能少用一色。

构造性证明把问题转化为寻找合适次序与分块，并可发展为线性时间的 Brooks 着色算法；线性时间结论需要实现相应的结构步骤，单独一次任意顺序的贪心扫描并无这一保证。完全图理路完全图Complete graph每一对不同顶点都恰有一条边相连的有限简单无向图。检测和连通分量分解则帮助先识别适用范围。