布鲁克斯定理

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

选择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}$ 恰当染色。

G是k正则图但有割点

假设割点为${\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}$ 恰当染色。

G是k正则图且無割点

由于${\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=只需其一 (帮助)