布鲁克斯定理

图论中，布鲁克定理（英語：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.