四色定理的最終證明

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

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

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

定義：當(dāng)無環(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]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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