布魯克斯定理

圖論中，布魯克定理（英語：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.