布鲁克斯定理

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

 背景 

 图染色数 

考慮為的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图中任意两个顶点，如果，那么所染成的颜色不同。

对于图，如果存在一个种颜色的恰当染色方案，称可染色（或「可着色」）。在所有满足条件的中，称最小的那个稱為染色數。

 图最小染色数和图最大度数关系 
圖的最大度記作。对于任意图，始终成立。但是这个上界并不足够紧。而布鲁克斯定理提供了一个更紧的上界。

图着色问题有一个贪心染色法（），将颜色标号为，将图G的顶点排序为，按顺序对顶点进行染色。染時，其邻居至多有個，所以已染色的鄰居中，至多衹用了種色，尚有某種色未用，可选择該種色作为的着色。

根据布鲁克斯定理，不等式取等当且仅当G为完全图或奇环。当G为完全图时，，，当G为奇环时，，，均满足。

 定理敍述 
如果是一个连通图，而且不是奇环或者完全图，那么。其中是图的最小着色数，是图中点的最大度数。

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

记。当的时候，是完全图。当的时候，由于不是奇环，那么要么是一条路径，或者偶环。此时。所以，衹需从开始考虑。分下列三種情況：

 G不是k正则图 

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

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

然后可以用上述贪心染色算法对图进行染色。染色顺序为：先染中的点，再染中的点，一直这么下去直到染完中的点。这种算法使用种颜色就能完成。当染到点時，在中至少有一个邻居，所以邻居中至多只有个被染色过，所以能对进行染色。

当染点的时候，由于，邻居中至多只有个被染色过，所以同样能对进行染色。所以用种颜色对恰当染色。

 G是k正则图但有割点 

假设割点为，那么就不是连通图，设有个連通分量。对于任意一个连通分支，考虑。由于在的度數小於，。由前述贪心染色算法可知，可染色。然后只需令这些染色方案中所染的颜色一样（如果不一样，将所有点染的颜色重新排列一下），就能拼成的染色方案，所以可用种颜色对恰当染色。

G是k正则图且無割点

由于中没有割点，是2连通图。斷言可以找到一个顶点，使得它有两个邻点，满足不相邻，且连通。如果这样的存在，就可以先將染成同色，然後貪心地為其他點染色，使最後染。这样貪心染法衹用不超過種色，因为除之外的点，只有小于等于个邻点排在它前面，而又有兩個邻点同色，故的鄰域衹用前種色，尚有餘下顏色可用。以下說明為何有此種。

如果是3连通的，則可以選取距離為2的兩點（因為不是完全圖），及其公共鄰點。如此有，又由于是3连通的，是连通图，即為所求。

僅剩是2连通但不是3连通的情況。此時有頂點使僅為1連通，考慮各個，之間以割點連接，組成一棵樹。因為不是2連通，該樹至少有兩個叶区块（），設為。又因为无割点，所以的每一个叶区块中，必有某個非割點與相邻。於是，可以在中各取的鄰點，使不是的割点。如此，不相邻（否則屬同一雙連通分支），且连通。因为，所以连通。證畢。

 参考文献 

Category:图染色
Category:组合数学
Category:理论计算机科学
Category:数学定理