布鲁克斯定理

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

背景

图染色数

主条目：图着色问题

考虑为$G$的顶点染色，而使每边的两端不同色。以符号表示，条件是：对于图$G$中任意两个顶点$u,v$，如果$uv\in E(G)$，那么$u,v$所染成的颜色不同。

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

图最小染色数和图最大度数关系

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

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

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

定理叙述

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

定理证明

此处给出洛瓦兹·拉兹洛的一个证明（亦见诸）。

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

G不是k正则图

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

若要避免术语“DFS”，可以构造下列集合$\{S_{i}\}$直到里面包含$G$中所有顶点：

${\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}}$

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

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

G是k正则图但有割点

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

G是k正则图且无割点

由于$G$中没有割点，$G$是2连通图。断言可以找到一个顶点$u$，使得它有两个邻点$v_{1},v_{2}$，满足$v_{1},v_{2}$不相邻，且$G-\{v_{1},v_{2}\}$连通。如果这样的$u,v_{1},v_{2}$存在，就可以先将$v_{1},v_{2}$染成同色，然后贪心地为其他点染色，使$u$最后染。这样贪心染法只用不超过$k$种色，因为除$u$之外的点，只有小于等于$k-1$个邻点排在它前面，而$u$又有两个邻点$v_{1},v_{2}$同色，故$u$的邻域只用前$k-1$种色，尚有余下颜色可用。以下说明为何有此种$u,v_{1},v_{2}$。

如果$G$是3连通的，则可以选取距离为2的两点$v_{1},v_{2}$（因为$G$不是完全图），及其公共邻点$u$。如此有$v_{1}v_{2}\notin E(G)$，又由于$G$是3连通的，$G-\{v_{1},v_{2}\}$是连通图，即为所求。

仅剩$G$是2连通但不是3连通的情况。此时有顶点$u$使$G-u$仅为1连通，考虑$G-u$各个双连通分支，之间以割点连接，组成一棵树。因为$G-u$不是2连通，该树至少有两个叶区块（leaf block），设为$B_{1},B_{2}$。又因为$G$无割点，所以$G-u$的每一个叶区块中，必有某个非割点与$u$相邻。于是，可以在$B_{1},B_{2}$中各取$u$的邻点$v_{1},v_{2}$，使$v_{1},v_{2}$不是$G-u$的割点。如此，$v_{1},v_{2}$不相邻（否则$B_{1},B_{2}$属同一双连通分支），且$G-\{u,v_{1},v_{2}\}$连通。因为$k\geq 3$，所以$G-\{v_{1},v_{2}\}$连通。证毕。

参考文献

• Rigo, Michel. Advanced graph theory and combinatorics. London, UK. 2008: 90–92. ISBN 978-0-387-79711-3. 
• Bondy, J. A. Graph theory. New York: Springer. 2008: 359-363. ISBN 978-1-84628-969-9.