布鲁克斯定理

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

背景

图染色数

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

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

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

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

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

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

定理敍述

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

定理证明

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

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

G不是k正则图

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

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

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

然后可以用上述贪心染色算法对图$G$进行染色。染色顺序为：先染$S_l$中的点，再染$S_{l-1}$中的点，一直这么下去直到染完$S_0$中的点。这种算法使用$l$种颜色就能完成。当染到点$u\in S_i(i\ne 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^{\prime }=G-\{u\}$就不是连通图，设$G^{\prime }$有$t$个連通分量$G_1,G_2,\dots ,G_t$。对于任意一个连通分支$G_i$，考虑$H_i=G_i\cup \{u\}$。由于$u$在$H_i$的度數小於$k$，$\mathrm{\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$各個Template:Le，之間以割點連接，組成一棵樹。因為$G-u$不是2連通，該樹至少有兩個叶区块（Template:Lang），設為$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\ge 3$，所以$G-\{v_1,v_2\}$连通。證畢。

参考文献

• Template:Cite book
• Template:Cite book