图论中，布鲁克定理（英語：Brooks' theorem）^[1] 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。

考慮為${\displaystyle G}$的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图${\displaystyle G}$中任意两个顶点${\displaystyle u,v}$，如果${\displaystyle uv\in E(G)}$，那么${\displaystyle u,v}$所染成的颜色不同。

对于图${\displaystyle G}$，如果存在一个${\displaystyle k}$种颜色的恰当染色方案，称${\displaystyle G}$可染${\displaystyle k}$色（或「${\displaystyle k}$可着色」）。在所有满足条件的${\displaystyle k\in \mathbb {Z_{+)) }$中，称最小的那个${\displaystyle k}$稱為染色數${\displaystyle \chi (G)}$。

圖${\displaystyle G}$的最大度記作${\displaystyle \Delta (G)}$。对于任意图${\displaystyle G}$，${\displaystyle \chi (G)\leq \Delta (G)+1}$始终成立。但是这个上界并不足够紧。而布鲁克斯定理提供了一个更紧的上界。

图着色问题有一个贪心染色法（greedy coloring）^[2]，将颜色标号为${\displaystyle 1,2,...,\Delta (G)+1}$，将图G的顶点排序为${\displaystyle v_{1},v_{2},...,v_{n))$，按顺序对顶点${\displaystyle v_{i))$进行染色。染${\displaystyle v_{i))$時，其邻居至多有${\displaystyle \Delta (G)}$個，所以已染色的鄰居中，至多衹用了${\displaystyle \Delta (G)}$種色，尚有某種色未用，可选择該種色作为${\displaystyle v_{i))$的着色。

根据布鲁克斯定理，不等式${\displaystyle \chi (G)\leq \Delta (G)+1}$取等当且仅当G为完全图或奇环。当G为完全图时，${\displaystyle \chi (G)=n}$，${\displaystyle \Delta (G)=n-1}$，当G为奇环时，${\displaystyle \chi (G)=3}$，${\displaystyle \Delta (G)=2}$，均满足${\displaystyle \chi (G)=\Delta (G)+1}$。

如果${\displaystyle G}$是一个连通图，而且${\displaystyle G}$不是奇环${\displaystyle C_{2n+1))$或者完全图${\displaystyle K_{n))$，那么${\displaystyle \chi (G)\leq \Delta (G)}$。其中${\displaystyle \chi (G)}$是图${\displaystyle G}$的最小着色数，${\displaystyle \Delta (G)}$是图${\displaystyle G}$中点的最大度数。

此處给出洛瓦兹·拉兹洛^[3]的一个证明（亦見諸^[4]）。

记${\displaystyle k=\Delta (G)}$。当${\displaystyle k=0,1}$的时候，${\displaystyle G}$是完全图。当${\displaystyle k=2}$的时候，由于${\displaystyle G}$不是奇环，那么${\displaystyle G}$要么是一条路径${\displaystyle P}$，或者偶环${\displaystyle C_{2n))$。此时${\displaystyle \chi (G)=2=\Delta (G)}$。所以，衹需从${\displaystyle k\geq 3}$开始考虑。分下列三種情況：

选择G中度小于k的点${\displaystyle v_{0))$最后染色。由於${\displaystyle G}$連通，有某種排序方式使得除${\displaystyle v_{0))$之外，每个节点都有一个邻点排在它的后面：例如从${\displaystyle v_{0))$出发对图G进行深度优先遍历，按照DFS序的逆序排列G的节点。故只有小于等于k - 1个邻点排在它前面，这样，只有小于等于k - 1个邻点排在它前面，而${\displaystyle d(v_{0})\leq k-1}$，故也只有小于等于k - 1个邻点排在它前面，按該次序的貪心染色最多衹用k種色。

若要避免術語「DFS」，可以构造下列集合${\displaystyle \{S_{i}\))$直到里面包含${\displaystyle G}$中所有顶点：

${\displaystyle {\begin{aligned}S_{0}&={v_{0))\\S_{1}&=N(v_{0})\\S_{2}&=N(S_{1})-S_{1}-S_{0}\\\dots \\S_{l}&=N(S_{l-1})-S_{l-1}-S_{l-2}\dots -S_{0}\end{aligned))}$

然后可以用上述贪心染色算法对图${\displaystyle G}$进行染色。染色顺序为：先染${\displaystyle S_{l))$中的点，再染${\displaystyle S_{l-1))$中的点，一直这么下去直到染完${\displaystyle S_{0))$中的点。这种算法使用${\displaystyle l}$种颜色就能完成。当染到点${\displaystyle u\in S_{i}(i\neq 0)}$時，${\displaystyle u}$在${\displaystyle S_{i-1))$中至少有一个邻居，所以${\displaystyle u}$邻居中至多只有${\displaystyle k-1}$个被染色过，所以能对${\displaystyle u}$进行染色。

当染点${\displaystyle v_{0))$的时候，由于${\displaystyle d(v_{0})<k}$，${\displaystyle v_{0))$邻居中至多只有${\displaystyle k-1}$个被染色过，所以同样能对${\displaystyle v_{0))$进行染色。所以用${\displaystyle k}$种颜色对${\displaystyle G}$恰当染色。

假设割点为${\displaystyle u}$，那么${\displaystyle G'=G-\{u\))$就不是连通图，设${\displaystyle G'}$有${\displaystyle t}$个連通分量${\displaystyle G_{1},G_{2},\dots ,G_{t))$。对于任意一个连通分支${\displaystyle G_{i))$，考虑${\displaystyle H_{i}=G_{i}\cup \{u\))$。由于${\displaystyle u}$在${\displaystyle H_{i))$的度數小於${\displaystyle k}$，${\displaystyle \Delta (H_{i})<k}$。由前述贪心染色算法可知，${\displaystyle H_{i))$可染${\displaystyle k}$色。然后只需令这些染色方案中${\displaystyle u}$所染的颜色一样（如果不一样，将所有点染的颜色重新排列一下），就能拼成${\displaystyle G}$的染色方案，所以可用${\displaystyle k}$种颜色对${\displaystyle G}$恰当染色。

由于${\displaystyle G}$中没有割点，${\displaystyle G}$是2连通图（英语：Biconnected graph）。斷言可以找到一个顶点${\displaystyle u}$，使得它有两个邻点${\displaystyle v_{1},v_{2))$，满足${\displaystyle v_{1},v_{2))$不相邻，且${\displaystyle G-\{v_{1},v_{2}\))$连通。如果这样的${\displaystyle u,v_{1},v_{2))$存在，就可以先將${\displaystyle v_{1},v_{2))$染成同色，然後貪心地為其他點染色，使${\displaystyle u}$最後染。这样貪心染法衹用不超過${\displaystyle k}$種色，因为除${\displaystyle u}$之外的点，只有小于等于${\displaystyle k-1}$个邻点排在它前面，而${\displaystyle u}$又有兩個邻点${\displaystyle v_{1},v_{2))$同色，故${\displaystyle u}$的鄰域衹用前${\displaystyle k-1}$種色，尚有餘下顏色可用。以下說明為何有此種${\displaystyle u,v_{1},v_{2))$。

如果${\displaystyle G}$是3连通的，則可以選取距離為2的兩點${\displaystyle v_{1},v_{2))$（因為${\displaystyle G}$不是完全圖），及其公共鄰點${\displaystyle u}$。如此有${\displaystyle v_{1}v_{2}\notin E(G)}$，又由于${\displaystyle G}$是3连通的，${\displaystyle G-\{v_{1},v_{2}\))$是连通图，即為所求。

僅剩${\displaystyle G}$是2连通但不是3连通的情況。此時有頂點${\displaystyle u}$使${\displaystyle G-u}$僅為1連通，考慮${\displaystyle G-u}$各個雙連通分支（英语：biconnected component），之間以割點連接，組成一棵樹。因為${\displaystyle G-u}$不是2連通，該樹至少有兩個叶区块（leaf block），設為${\displaystyle B_{1},B_{2))$。又因为${\displaystyle G}$无割点，所以${\displaystyle G-u}$的每一个叶区块中，必有某個非割點與${\displaystyle u}$相邻。於是，可以在${\displaystyle B_{1},B_{2))$中各取${\displaystyle u}$的鄰點${\displaystyle v_{1},v_{2))$，使${\displaystyle v_{1},v_{2))$不是${\displaystyle G-u}$的割点。如此，${\displaystyle v_{1},v_{2))$不相邻（否則${\displaystyle B_{1},B_{2))$屬同一雙連通分支），且${\displaystyle G-\{u,v_{1},v_{2}\))$连通。因为${\displaystyle k\geq 3}$，所以${\displaystyle G-\{v_{1},v_{2}\))$连通。證畢。

1. ^ Brooks, R. L., On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society（英语：Mathematical Proceedings of the Cambridge Philosophical Society）, 1941, 37 (2): 194–197, doi:10.1017/S030500410002168X 
2. ^ Mitchem, John, On various algorithms for estimating the chromatic number of a graph, The Computer Journal（英语：The Computer Journal）, 1976, 19 (2): 182–183, MR 0437376, doi:10.1093/comjnl/19.2.182 
3. ^ Lovász, L., Three short proofs in graph theory, Journal of Combinatorial Theory（英语：Journal of Combinatorial Theory）, Series B, 1975, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1 
4. ^ Douglas B.West. Introduction to Graph Theory. Pearson Enducation. 2002. ISBN 81-7808-830-4. 

• Rigo, Michel. Advanced graph theory and combinatorics. London, UK. 2008: 90–92. ISBN 978-0-387-79711-3.  |author1=和|last1=只需其一 (帮助)
• Bondy, J. A. Graph theory. New York: Springer. 2008: 359-363. ISBN 978-1-84628-969-9.  |author1=和|last1=只需其一 (帮助)