四色定理的最終證明

摘 要： 本文使用三角形結構平面圖僅有延伸結構和輪形結構兩大類不可避免構形集、顏色關系傳遞、圖收縮和順序著色法解決了四色定理的證明和應用。

關鍵詞： 不可避免構形集 顏色沖突 圖收縮 順序著色法

《四色定理證明新方法》一文已經證明（簡介如下）[1] ：

定義：當無環的內小面均為C 的平面連通圖稱之為三角形結構平面圖。其中無輪形結構者稱之為延伸結構，用E 表示。已知輪形結構用W 表示。

定理1：三角形結構平面圖僅有延伸結構和輪形結構兩大類不可避免構形集[2]。

證：可逐個增加三角形結構構造三角形結構平面圖，結合歐拉公式使用數學歸納法：（1）當選擇增加一個頂點和兩條邊時產生的是延伸結構，即 f = e+2-v-1+1；（2）當選擇增加一個條邊時產生一個輪形結構，即f = e+1-v+1（歐拉公式均成立）。此外，不可能有多于兩個頂點或三邊的情況（會產生割點）。

引理1：輪形結構子圖色數≤4[3]。

定理2：延伸結構子圖是有序圖，其中，E 是傳遞顏色的因子。延伸結構子圖色數=3。

證：因為在兩個相鄰的三角形結構內不在公共邊的兩個頂點必然同色，故稱E 是傳遞顏色的因子。使用數學歸納法，假設第n個頂點，延伸結構子圖En為有序3-色圖；第n+1個頂點必在某E 之中，并與對應的頂點同顏色。即E 仍為有序圖。顯然，E 仍為3色圖。

定理3：在3色圖中，當延伸結構子圖的兩個相同顏色的頂點再有鄰接邊就發生顏色沖突，但它可以通過調整輪形結構的位置消除沖突。

證：在一個延伸結構子圖中，任意兩個相同顏色的頂點加一鄰接邊，則構成顏色沖突。當此邊與原來的頂點和邊組成K ， 可將中心頂點變成第四色。否則此邊與原來的頂點和邊組成一個大于K 的輪形結構，此時可以調整輪形結構的位置，消除顏色沖突（見下圖）。

由定理4，可知，僅僅證明不可避免構形集和所有構形的可約還是不充分的，必須證明如何鑒別顏色沖突及如何消除顏色沖突才是充分的證明。下面便是本文利用順序著色法解決這一難題。

順序著色法定義： 對于一個k色圖，根據頂點顏色關系、按照一定順序能給頂點實現正常k著色，則稱此順序為正確的著色順序，此方法稱為順序著色法。顯然，利用順序著色法進行著色，后面著色的頂點顏色是順從于前面著色的頂點顏色關系的。換句話說，在分析前面著色的頂點顏色關系時，后面著色的頂點可以暫時不考慮它們的存在，即可以使用這一原則將復雜的圖收縮為簡單的圖。那么順序著色法的實際操作步驟就包括：1.圖收縮：將復雜的圖化為簡單的圖，進行分析關鍵頂點的顏色關系；2.確定正確的輪形結構位置；3.恢復被收縮的頂點和邊，按照正確的著色順序完成原圖的正常4著色。

順序著色法的依據和實際操作步驟為：.

1.由于K 的特點，不管外圈三個頂點是什么顏色，中心頂點都可以用第四色著色。因此在4色圖中可以將K 看做K 處理，可將復雜的原圖收縮為無K 的3色簡單圖。

2.在簡單圖中將所有輪形結構的中心頂點用白色著色，再將所有白色中心頂點（及邊）刪去， 同時刪去剩下的自由頂點就能使用圖收縮的方法得到一個限制色數為3色的僅含若干個延伸結構子圖和它們之間的鄰接邊組成的簡單圖。

3.經過收縮得到的簡單圖中，根據延伸結構子圖是有序3色圖（E4是傳遞頂點顏色的最小因子），當遇到兩個相同顏色的頂點之間再有鄰接邊而形成沖突鏈，而產生頂點顏色沖突。這樣就可以判定顏色沖突的頂點位置，同時可以根據定理3重新調整輪形結構的位置消除沖突，那么便可以得到一個沒有顏色沖突的正常4著色的4色圖。

4.恢復所有輪形結構的中心頂點和邊，恢復所有k 和自由頂點并著色，就能得到一個與原圖同構的正常4著色的4色圖。

上圖便是一個順序著色法例案。根據以上幾點就可證明：

定理5：任何復雜的三角形結構平面圖都可以使用以上順序著色法步驟實現正常4著色。 即三角形結構平面圖的色數不大于4。

定理6：由于平面連通圖的色數不大于三角形結構平面圖的色數[4]， 因此任何平面連通圖的色數不大于4。

至此， 四色定理的終結證明大功告成.。

結論：1.4色平面圖的頂點顏色關系是以具有正確輪形位置的無K 簡單圖為基礎的，而嵌套的K構成更復雜的平面圖，但平面圖的色數仍等于4。

2.由于本證明是針對任何復雜三角形結構平面圖為目的，延伸結構可以是任意復雜的圖，因此該證明不是個例，而是具有普遍代表性的。

3.討論頂點的正常著色僅證明不可避免構形集和所有構形的可約還是不充分的。必須同時證明由構形組合的各種子圖還可能產生頂點顏色沖突，以及如何消除才是充分的四色定理證明。

4.本證明展現了一個不依賴計算機的四色定理證明及應用新方法。

參考文獻：

[1] 梁增勇.四色定理證明新方法[DB/CD]. 百度文庫，2013，http：/wenku.com/user/....

[2] R.Balakrishnan ， K.Ranganathan，， A Textbook of Graph Theory[M].北京：科學出版社，2011：187-188.

[3] 王樹禾.圖論[M] .科學出版社，北京：2004：90.

[4] 屈婉玲，耿素云，張立昂.離散數學[M].北京：高等教育出版社，2008：324-325.