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

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

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

定義：當無環(huán)的內(nèi)小面均為C 的平面連通圖稱之為三角形結(jié)構(gòu)平面圖。其中無輪形結(jié)構(gòu)者稱之為延伸結(jié)構(gòu)，用E 表示。已知輪形結(jié)構(gòu)用W 表示。

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

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

引理1：輪形結(jié)構(gòu)子圖色數(shù)≤4[3]。

定理2：延伸結(jié)構(gòu)子圖是有序圖，其中，E 是傳遞顏色的因子。延伸結(jié)構(gòu)子圖色數(shù)=3。

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

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

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

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

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

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

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

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

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

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

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

定理5：任何復雜的三角形結(jié)構(gòu)平面圖都可以使用以上順序著色法步驟實現(xiàn)正常4著色。 即三角形結(jié)構(gòu)平面圖的色數(shù)不大于4。

定理6：由于平面連通圖的色數(shù)不大于三角形結(jié)構(gòu)平面圖的色數(shù)[4]， 因此任何平面連通圖的色數(shù)不大于4。

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

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

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

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

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

參考文獻：

[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] 屈婉玲，耿素云，張立昂.離散數(shù)學[M].北京：高等教育出版社，2008：324-325.