形式陈述

Brooks 定理断言：若 $G$$G$ 是连通有限简单图，最大度为 $\Delta$$\mathrm{\Delta }$，并且 $G$$G$ 既不是完全图也不是奇圈，则

$$ \chi(G)\le\Delta. $$$$\chi (G)\le \mathrm{\Delta }.$$

异常情形恰需要 $\Delta+1$$\mathrm{\Delta }+1$ 色：完全图 $K_{\Delta+1}$$K_{\mathrm{\Delta }+1}$ 的色数为 $\Delta+1$$\mathrm{\Delta }+1$，奇圈的最大度为二而色数为三。对不连通图可逐分量应用，整体色数是各分量色数的最大值。证明可按图的连通结构选取特殊顶点顺序作贪心着色，或用块分解和归纳处理。

直觉

普通贪心界给 $\Delta+1$$\mathrm{\Delta }+1$；Brooks 定理说明除两种高度紧绷的结构外，总能通过合适顺序省下一种颜色。

例子与边界

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

推论与应用

Brooks 定理改进局部度数着色界，并用于临界图、稀疏图算法和结构着色理论。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，Ch. 5, Brooks theorem。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，Ch. 5, Brooks theorem and critical graphs。