布鲁克斯定理

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