圖解四色定理-有解無憂

圖解四色定理
一、概述
1852年，英國數學家法蘭西斯.古德里最先提出四色猜想：“任何一張地圖只用4種顏色就能使具有共同邊界的國家著不同顏色”。
1976年，數學家凱尼斯.阿佩爾和沃夫岡.哈肯采用“放電法”程式、借助計算機運行1200小時驗證，首次證明了四色定理。
但如此簡潔的問題描述，與如此復雜的證明程序嚴重違和，一直有人希望能夠找到更簡單的、無需借助計算機的證明程序。
本文嘗試論述一種直接的、無需借助計算機驗算的四色定理證明。

二、關鍵概念
1) 正規地圖
正規地圖是指：沒有1個國家包圍其它國家，或沒有3個以上國家相遇于1點的地圖為正規地圖(維基百科中也稱為三度圖)。

如上圖所示，國家數量相同，在地圖中的位置也相同的情況下，正規地圖的著色數量一定不少于非正規地圖。本文提到的地圖默認指正規地圖。
2) 不可避免構形
1878年，數學家阿爾弗雷德.布雷.肯普(Alfred Kempe)發布了一份四色定理證明。肯普在證明中闡述了兩個重要概念，一直被視為證明四色定理的關鍵。第一個概念是“不可避免構形”，在任意正規地圖中至少有1個國家具有2、3、4或5個鄰國，不存在每個國家都有>=6個鄰國的正規地圖，也就是說，二、三、四或五鄰國“構形”是不可避免的，每張地圖中都必然含有這4種不可避免構形中的1個或多個。
證明程序參考了歐拉公式(v:頂點-e:邊+r:面=2)，得出任意平面地圖中至少存在1個國家，其鄰國數量<=5：
(1) 歐拉公式: v-e+r=2；
(2) 平面地圖: 3*v<=2*e；
(3) 將歐拉公式代入公式(2)得: 3*r-e>=6；
(4) 假設地圖中每個面平均有x條邊，有: x*r=2*e；
(5) 將(4)代入(3)得: 6*r-x*r>=12，從而得平均邊數: x<6；
因此，任意平面地圖中一定至少存在1個國家，其鄰國數量<=5；
3) 構形可約
肯普提出的另一個概念是“可約”，即對不可避免構形(二、三、四、五鄰國構形)中心的國家做任意約減、恢復操作時，不會增加地圖的著色數量。
在持續約減不可避免構形中心的國家時，地圖中其余的>=6鄰國構形的相鄰國家數量會降低，剩余的國家數量也會逐漸減少，最侄訓得到一份國家數量有限、且僅包含不可避免構形的地圖。如果約減到最終的地圖是四色足夠的，那么對約減地圖做逆序恢復操作，則恢復到初始狀態的地圖也一定四色足夠的。
二、三鄰國構形約減、恢復區域中心的國家并不會影響地圖其它區域著色。被約減的四鄰國構形在恢復時，可能會影響地圖上的其它區域著色，但是利用肯普變換可以保證并不增加地圖的著色數量。

肯普在論文中描述五鄰國構形區域也一定可約。如下圖所示，如果約減后的構形區域5個鄰國已經占滿4種顏色，當不存在A-C、或者不存在A-D肯普鏈時，可將A色換著C、D色來恢復五鄰國構形，當同時存在A-C、A-D兩條肯鏈時，可按如下方式恢復五鄰國構形(保持五鄰國構形區域6個國家著4色、且不增加地圖其它區域著色數量)。

4) 希伍德反例和五色定理
1890年，珀西.約翰.希伍德(Heawood)指出“肯普鏈”方法中的缺陷，并構造出無法使用肯普鏈變換著4色的區域五鄰國構形地圖實體，稱為希伍德反例。

在希伍德構造的最小16國反例圖中，目標五鄰國構形周圍的5個相鄰國家，存在A-C與A-D兩條“交叉”肯普鏈。對該地圖區域構形周圍的5個鄰國使用肯普鏈變換著色，4種顏色在構形周圍的5個鄰國中恰好能回圈往復，無法降到3種顏色，從而無法證明該五鄰國構形區域(共6個國家)可被著4色。
對于該缺陷，肯普未能給出修復策略，因此四色猜想惜未得證。但相對較弱的五色定理命題由此得證。
希伍德同時提出猜想：在任意可定向曲面上，最多只用

種顏色就能為任意的地圖染色，其中k是曲面的虧格。當k=0的時候，這個猜想就變成了四色猜想。當地圖中存在“飛地”時(地圖中某兩個不相鄰的地區屬于同一個國家，必須著同色)，有K≥1。在1968年，杰拉德.格爾和J.W.T.楊格斯最終證明了這個猜想在k≥1時的情況。
直到1976年，數學家凱尼斯.阿佩爾和沃夫岡.哈肯采用“放電法”程式，經過計算機1200小時的驗證，首次得到一個完全的證明，四色猜想也終于成為四色定理。
這是首個主要借助計算機證明的定理，一開始未被普遍接受，因為大眾認為這個證明無法被直接驗證。盡管隨著計算機的普及，人們對計算機輔助證明更能接受，但仍有人希望能夠找到簡潔的、不借助計算機的證明程序。

三、證明程序
下圖為希伍德在虧格為1的地圖上構造出7個兩兩相鄰國家的示意。
借鑒該方法，我們嘗試分析五鄰國構形的最小著色數量。

若地圖中某個五鄰國構形區域可著4色(包含中心、及周圍共6個國家)，則該五鄰國構形周圍的5個國家只能著3色(下文簡稱“5鄰3色”)，共有5種等價形態(如下圖3色：A、B、C)。

當構形周圍5個國家以指定順序著3色時(A、B、C)，可以輕易構造出必須使用5種顏色的地圖：

但調整構形周圍5個國家的著色順序(仍為A、B、C三種顏色)，我們發現地圖上國家間的鄰接關系會破壞消減，調整后的地圖用4種顏色即可完成著色。
這種“東方不亮西方亮、黑了南方有北方”的現象，在構形周圍5個國家以指定順序著4色時也同樣存在(不考慮對構形中心的國家著色，下文簡稱“5鄰4色”)：

可能性說明：地圖區域五鄰國構形以外國家數量超過4個、且構形指定“5鄰3色”時，可能無法構造出有5個兩兩相鄰國家的地圖，若能證明此點，也能證明五鄰國構形可約。本文未對此可能點深入分析。

根據五色定理，對于任意平面地圖上的區域五鄰國構形，在不考慮對構形中心的國家著色時，該構形周圍的5個鄰國，一定可以著4色。因為構形周圍“5鄰4色”共有5種等價組合，這5種等價地圖中，至少有3種地圖存在四色足夠的著色方案：

推證：我們知道四鄰國構形一定可約，四鄰國構形周圍的4個國家也一定可以著3色(不考慮構形中心國家)。因為構形周圍“4鄰3色”共有2種等價組合，那么這兩種等價組合中，至少有1種地圖是四色足夠的。
而構形周圍“5鄰4色”的5種等價地圖中，互相存在交叉斥補關系。根據“4鄰3色”2種等價組合中必有1種地圖四色足夠推斷，“5鄰4色”的5種等價地圖中一定存在不少于5/2，即>=3種地圖是四色足夠的。

如需證明包含五鄰國構形的地圖可著4色，則構形周圍“5鄰3色”的5種等價地圖中，至少要存在1種地圖是四色足夠的。
也即：如果任意地圖區域五鄰國構形“5鄰3色”的5種等價組合中，至少存在1種地圖是四色足夠的，則五鄰國構形一定可約。
下面求解任意五鄰國構形“5鄰3色”的5種等價地圖中，最少的著色數量：