切實可行的四色定理證明新方法

【摘要】本文簡單介紹用圖論的方法證明三角形結構連通圖的不可避免構形集，同時用順序配色的方法證明三角形結構連通圖的色數≤4，也就證明平面圖的色數≤4.為四色定理證明和應用找到了切實可行的新方法.

【關鍵詞】 三角形結構連通圖； 不可避免構形集； 延伸結構； 輪形結構； 順序配色法

【中圖分類號】O156

1.前 言

四色猜想是世界數學界關注的問題，給出四色定理無需借助于計算機的證明仍然是一個未獲解決的數學難題.我們已知四色定理可通過證明平面連通圖G的色數≤4來實現.而平面連通圖的色數不大于由它增加邊而導出的三角形結構連通圖G （triangulated graph）的色數.因此，只需證明任意三角形結構連通圖的χ（G）≤4，即解決問題.

2.兩大不可避免構形集

定理1 三角形結構連通圖僅有延伸和輪形兩種結構方式.

證 （1）我們可以逐個增加三角形構造三角形結構子圖，由歐拉公式可證明，為了增加一個三角形（面）：1）當增加一個頂點和兩條邊得到的是延伸結構.2）而增加一條邊會產生一個新輪形結構.（2）延伸和輪形兩種結構的組合結果還是這兩種類型的結構.因此三角形結構連通圖只有延伸結構和輪形結構兩大不可避免構形集.

引理1 輪圖色數≤4.

定理2 延伸結構子圖色數=3.

證 如上用逐個增加三角形構造延伸結構子圖，每一個新頂點都可以用與同一個三角形中另兩個頂點不同的顏色，可通過數學歸納法很容易地證明延伸結構子圖色數=3.

3.圖的簡化和擴展

任何復雜的延伸結構和輪形結構的鄰接可簡化歸納為3個模塊和扇形模塊（見下圖），由它們的擴展圖組合可以構成任意的三角形結構子圖.

4.順序配色法

首先，應先對圖G做好一個初步的的規劃圖（預分配）是形成輪形間隔延伸結構的布局，使之出現更多小的延伸結構.然后逐個對延伸結構進行分部配色，直至完成落實全部圖的頂點的正常4-著色，這一方法稱之為順序配色法（見下圖）.圖Ⅰ、Ⅱ 表示一組一個延伸結構與輪形結構鄰接的部分配色的方法：圖中Ⅰ下部Y12是前面已經著好色的延伸結構，上面的Y12是本次需要配色的延伸結構，中間隔著4個輪形（注：為了分清輪形與延伸結構，將所有輪形的邊用淺色線表示）.圖中Ⅱ是一般情況下正常4-著色的結果.輪形中心頂點用白色.延伸結構的頂點用另外三色.當使用一般的方法不能對Y12正常著色，就可以采用圖中Ⅲ的方法，將輪形結構重新排列，由于有足夠的位置插入新輪形將子圖隔離成獨立的延伸

結構碎塊（互相不再有顏色沖突），由于圖下邊頂點保持顏色不變，使前后兩個子圖能很好地銜接合并無顏色沖突.由于延伸結構色數=3，輪圖色數≤4，結果母圖G的色數也≤4.

通過以上分析證明，不管任何復雜的平面圖都可以轉換成三角形結構的連通圖進行分析正確安排輪形結構的位置，實施正常4-著色.這也就證明了任何平面圖的色數≤4.

【參考文獻】

[1]王數禾.圖論 [M].北京：科學出版社，2004.

[2]屈婉玲， 耿素云， 張立昂. 離散數學[M]. 北京： 清華大學出版社， 2005.