動機
一個圖可以有一個度數很高的頂點,卻仍然容易著色。對合適的貪心次序而言,重要的不是初始最大度數,而是在剩下的圖中能否總能刪去一個低度頂點。把這樣的刪除次序反過來,就能在每一步限制已著色鄰點的數目。
歐拉(Euler)的平面圖邊數上界正好提供這種可重複使用的低度保證,並即時推出六種顏色足夠。要得到五種顏色,唯一的困難在於度數為五的頂點:它的鄰點可能已經用盡所有顏色。在一個較小的平面圖中收縮兩個不相鄰的鄰點,會迫使它們共用一種顏色,從而為被刪去的頂點騰出一種顏色。證明將說明,為甚麼普通的收縮在沒有額外處理時不能總是還原。
論證使用由歐拉公式得到的簡單平面圖邊數上界 。本文不聲稱證明了四色定理。
定義
定義 10.4.1
(退化度與刪除次序)
對非負整數 ,若有限簡單圖的每個非空子圖都含有一個度數至多為 的頂點,則稱該圖為 -退化的。這裏的度數是在該子圖內部計算的。退化刪除次序是指每一步刪去一個當前度數至多為 的頂點,直至沒有頂點為止。
正常頂點著色給每個頂點指定一種顏色,並使相鄰頂點的顏色不同。按給定次序的貪心著色,是給每個頂點指定第一種尚未被其已著色鄰點使用的顏色。
檢驗退化性只需檢驗導出子圖。事實上,在選定頂點集上的任何子圖中,各頂點的度數都不超過該頂點集上導出子圖中的度數。導出子圖中的低度頂點,在進一步去掉一些邊之後仍是低度頂點。因此,刪去頂點或邊時該性質得以保持。
定義 10.4.2
(邊收縮及簡單圖的整理)
收縮一條邊,是把它的兩個端點等同為一個頂點,保留其餘所有關聯關係;若希望結果為簡單圖,則再刪去自環並合併重邊。平面性得以保持:在平面嵌入中,在該邊及其端點的一個細小鄰域內把所選的邊縮短,並讓關聯的邊端隨之移動。遠離新的公共端點之處,各曲線可以保持分離。刪去自環或重複的邊不會引入交叉。
這種局部作圖操作只說明收縮後的圖仍是平面圖,並不是把其著色提升回原圖的一般規則。如果原先相鄰的頂點後來被賦予合併頂點的同一種顏色,它們之間原有的邊就違反了正常性。我們將收縮一個由三個頂點構成的結構,並且只把顏色提升到原本不相鄰的兩個頂點上。
定理/命題
定理 10.4.3
(退化序給出受控的貪心著色)
一個圖是 -退化的,當且僅當其頂點有一種刪除次序,使每個頂點至多有 個排在其後的鄰點。把該次序反過來並貪心著色,至多使用 種顏色。每個有限簡單平面圖都是 5-退化的,因而是六可著色的。
對以鄰接表表示的平面圖輸入,維護度數的隊列可在 時間內給出刪除次序和一個六著色。該算法構造一個著色;僅僅找到這樣的次序,並不能證明任意輸入是平面圖。
定理 10.4.4
(透過收縮證明五色定理)
每個有限簡單平面圖都有一個由五種顏色構成的色板中的正常頂點著色。該結論包括非連通圖和空圖。證明使用歸納法、歐拉的度數上界,以及對一個五度頂點的兩個不相鄰鄰點的收縮。
六著色算法與五色存在性證明是兩種不同的產出,其構造也不同。後一個證明是構造性的,但這裏不斷言其重複收縮與提升的任何優化實現的複雜度上界。兩個定理都沒有說每個平面圖都需要五種顏色。
證明思路或證明
證明
(刪除次序與逆序貪心著色)
對 -退化圖,在剩下的導出子圖中重複選取低度頂點。它在當時的鄰點恰好就是它在刪除次序中排在其後的鄰點。反過來,給定這樣的次序,取任意非空子圖,選其中最早的頂點。它在該子圖中的所有鄰點都排在其後,故其在該子圖中的度數至多為 。這證明了等價性。
按相反的次序,每個頂點至多有 個已著色的鄰點。它們至多禁用 種顏色,於是 種顏色中至少還有一種可用。每當一個頂點被著色,它都避開所有先前已著色的鄰點。因此,每條邊的兩個端點一旦都被著色,顏色就不同。
證明
(平面圖的 5-退化性與線性六著色)
每個至少有三個頂點的非空簡單平面子圖都滿足已證明的上界 。其度數和為 ,因此有一個度數至多為五的頂點。當只有一個或兩個頂點時,由簡單性可直接得到同樣的結論。所有子圖仍然是平面的。因此,低度觀察不僅適用於開始時,而是可以重複使用,從而證明了 5-退化性。
對於線性時間的刪除算法,先初始化所有頂點的當前度數,並建立由度數至多為五的頂點組成的隊列。刪去其中一個頂點時,將每個尚存鄰點的度數減一,並在某個鄰點的度數首次降到五時把它加入隊列。度數從不增加,因此每個頂點只需入隊一次。每條邊只引起常數次度數更新,而平面圖的低度保證使得只要還有頂點,隊列就不會為空。在反序中,檢查各鄰點並使用一個含六項的顏色標記,這同樣花費 。
證明
(收縮一對不相鄰鄰點得到五著色)
對五著色,對頂點數進行歸納。空圖已經染好色。在非空平面圖中,選取度數至多為五的頂點 。若其度數至多為四,則刪去它,由歸納法給較小的圖著色,再給它指定一種未出現在其至多四個鄰點上的顏色。
還需處理度數恰為五的情形。它的鄰點中有兩個,設為 ,彼此不相鄰。否則這五個鄰點會導出 ,而這在平面圖中不可能:其十條邊違反了五個頂點上簡單平面圖至多九條邊的上界。依次收縮 與 ,把 合併為一個頂點,並作簡單圖整理。所得的圖是平面圖且頂點數少二,所以由歸納法它有一個五著色。
還原除 以外的每個原頂點,讓 和 取得合併頂點的顏色,其餘頂點保持原色。這在 上是正常的。被還原的兩個頂點之間沒有邊,而且從其中任一個到其他原頂點的每條邊,都作為從合併頂點到該頂點的一條邊保留了下來。因此不可能再出現衝突。
在 的五個鄰點中, 現在共用一種顏色;其餘三個至多再貢獻三種顏色。因此在 處至多有四種顏色被禁用。選取第五種可用顏色,即完成歸納。合併頂點在收縮過程中代表 ,但提升著色時有意讓原來的 保持未著色,直至這最後一步。
證明透視
只有不相鄰的那一對繼承合併後的顏色
三個假設在三個不同位置用到。平面性經由簡單上界 提供度數至多為五的頂點 ;平面性又排除了 ,所以 有兩個鄰點 不相鄰。平面圖在收縮下封閉,才使歸納假設能用於合併 之後的圖;單靠 5-退化性並不足夠,因為 是 5-退化的。 與 不相鄰,才使提升是正常的:若有邊 ,它會連接兩個同色頂點;若把合併後的顏色也給 ,便會與 、 衝突,所以 暫不著色。
計數隨即完成歸納。提升之後,由於 與 同色, 的五個鄰點至多呈現四種顏色,五種顏色中便有一種空出。若有六個鄰點,同樣的做法可能留下多達五種被禁止的顏色;這就是論證需要度數五、而不只是某個小度數的原因。
為甚麼該證明不能變成四色定理的證明
歐拉的上界給出一個度數至多為五的頂點,但不能據此假定其度數至多為三。在五個鄰點中合併一對,把它們可能的顏色數降到四。這在五種顏色的色板中留下一種可用顏色,但在四種顏色的色板中可能一種也不剩。因此,這一歸納正好證明它所陳述的界。不能靠最後把色板大小改個標號而得到另一個定理。
收縮這一步用到的也不止退化性。它需要收縮後的較小圖仍留在平面圖類之內,這樣才能對該圖使用歸納。一個任意的 5-退化圖可能需要六種顏色,六頂點完全圖就是例子。該圖類在證明所用的圖運算下封閉;這種結構上的封閉性提供了僅由刪除次序所沒有的資訊。
例題詳解
例題 10.4.5
(退化度避免了過大的最大度數上界)
一個有一個中心和任意正數個葉子的星圖是 1-退化的。含邊的非空子圖有度數為一的葉子,無邊的子圖度數為零。先刪葉子再刪中心,然後反序著色:中心得到一種顏色,所有葉子得到第二種顏色。最大度數可以任意大,而這個次序始終只用兩種顏色。由於存在邊,一種顏色不可能足夠。
例題 10.4.6
(收縮五鄰點輪圖的中心)
取一個五頂點外圈 和中心 。選取不相鄰的外圈頂點 ,把它們與 合併為頂點 。其餘頂點為 。在整理後的圖中, 與這三個頂點都相連,另外還有邊 。
給 染顏色一, 染顏色二, 染顏色三。把顏色一提升到 ,其餘保持不變,再給 染顏色四。這是原圖的一個正常著色。這裏確實需要四種顏色:奇數長度的外圈至少需要三種,而這三種在與它們都相鄰的中心處全部被禁用。一般的五色上界對具體某個圖不必是緊的。
例題 10.4.7
(在樹上,壞的貪心次序可以使用任意多種顏色)
令 為單個有根頂點。對 ,取 的不相交副本,再添加一個新根,與它們的根相鄰。結果是一棵樹:每個舊分支恰好用一條邊連到新頂點。由歸納得 。
先按遞歸規定的次序給每棵複製的樹著色,最後給新根著色。被複製的各個根得到顏色一至 ,所以新根得到顏色 。因此這個貪心次序在一棵樹上用了 種顏色,儘管當 時這棵樹是可二著色的。一個平面圖得到很多種貪心顏色,可能只是因為處理次序不好;這並不推翻存在性上界。
概念視角結構
刪除與收縮使用不同種類的封閉性
低度頂點的刪除控制反序貪心的每一步。收縮則改變了在提升解時哪些頂點必須共用一種顏色。平面圖在這兩種運算下都保持平面性,從而可以對不同的較小圖使用歸納。每種運算都保持了下一步所需要的性質,而它們提升著色的規則並不相同。
常見錯誤
反例模式
子式的著色不能總是原封不動地提升
收縮三角形的一條邊。去掉由此產生的重邊之後,所得的圖是一條邊,可二著色。三角形卻不可二著色:它的第三個頂點與任一條邊的兩個端點都相鄰。把被收縮的相鄰端點以同一種顏色還原是行不通的。五色證明避開了這個錯誤:只讓原本不相鄰的鄰點共用一種顏色,並單獨給居中的頂點著色。
常見錯誤
(一個低度頂點不等於退化次序)
不要誤以為初始度數低就保證在所有剩餘的圖中都有低度次序。在 上接一個懸掛頂點:圖中有度數為一的頂點,但刪去它之後,剩餘每個頂點的度數都是四。這個圖是 4-退化而非 1-退化的,而且需要五種顏色。
常見錯誤
(次序找得到並不證明平面性)
不要以為一個著色或一個刪除次序能證明圖是平面的。對 ,隊列算法仍然找到每個頂點至多有五個後繼鄰點的次序,並輸出一個六著色;然而 有十五條邊,多於平面上界十二。
常見錯誤
(含自環的圖不在定理範圍內)
簡單性對度數和著色的陳述至關重要:含自環的圖在通常的相鄰端點規則下沒有正常頂點著色,無論調色板多大,因為帶自環的頂點與自身相鄰。
總結
退化度把重複刪除低度頂點轉化為受控的反序貪心次序。歐拉的上界為平面圖提供了這種次序,由此得到線性時間的六著色。經過細緻提升的收縮處理了五度頂點這一障礙,證明了五色定理,同時也正好說明了為甚麼同樣的論證不能證明四色定理。
練習
快速檢查
(證明六頂點完全圖是 5-退化的,但不是五可著色的。說明平面圖的收縮證明還用到了哪一條額外的性質。)
檢驗每個子圖的度數上界以及團的著色要求。
解答 · 答案
的每個子圖至多有六個頂點,因而度數至多為五,所以它是 5-退化的。六個頂點兩兩相鄰,因此需要六種不同的顏色。它不是平面圖,因為十五條邊超過了上界十二。平面圖的證明用到了平面性在收縮下的保持,以及所選鄰點之間不含五元團;這些事實不能僅由 5-退化性推出。
快速檢查
(解釋為甚麼僅僅得到一個度數至多為六的頂點,並不能透過合併一對不相鄰的鄰點來完成同樣的五色歸納。)
數一數合併之後鄰點可能具有的不同顏色數。
解答 · 答案
有六個鄰點時,合併一對不相鄰的鄰點,只迫使這兩個共用一種顏色。其餘四個鄰點可能再使用四種顏色,於是在被刪去的頂點處至多有五種顏色被禁用。這樣,五色色板中就沒有保證可用的空閒顏色。論證需要度數為五的結論,才能把被禁用的顏色數降到至多四。這說明了該證明的局限,並不是斷言每個度數為六的結構都真的需要六種顏色。
快速檢查
(證明對五頂點的奇圈,退化度給出的上界是緊的。給出一個明確的最優著色,並指出帶自環的版本為甚麼不在該定理的範圍之內。)
比較 2-退化性與沿奇圈交替使用兩種顏色的不可能性。
解答 · 答案
五圈的每個頂點度數為二,且每個子圖都有度數至多為二的頂點,所以它是 2-退化的。沿其五條邊交替使用兩種顏色,會回到起點而得到相反的所需顏色,這是不可能的。按圈的次序,顏色一、二、一、二、三給出一個有效的三著色。因此其色數為三,達到 。加上一個自環會使其端點與自身相鄰,所以沒有任何顏色能滿足正常性;所得的圖不是簡單圖,被排除在兩個定理的假設之外。