四色定理：偽證與推廣
這篇專欄，主要是我在看了一篇四色定理科普后寫出來的。因?yàn)槲覐脑u(píng)論區(qū)發(fā)現(xiàn)有些人證明了一些更弱的定理（比如“平面上不存在五個(gè)兩兩相鄰的國家”）便以為已經(jīng)解決，還有的人對(duì)其他情況的“n色定理”不是很熟悉。而現(xiàn)在的大部分科普卻往往忽視了這些點(diǎn)。因此我決定寫這一篇專欄，總結(jié)一下目前常見的一種偽證以及它問題，還有對(duì)其他方向的一些推廣。
我敢打包票，這篇專欄是目前B站對(duì)四色定理闡述最為詳細(xì)的一篇了。
問題介紹
“四色猜想”描述如下：
將一塊有限平面分成一些相鄰的區(qū)域（這里相鄰定義為至少有一條曲邊由兩個(gè)區(qū)塊共有，而非一個(gè)點(diǎn)），每個(gè)聯(lián)通區(qū)域稱為一個(gè)國家（也就是說，沒有現(xiàn)實(shí)地圖中“飛地”的問題），這樣的劃分結(jié)果稱為一個(gè)地圖。要求給地圖中每個(gè)國家上色，一個(gè)國家整體是一種顏色，相鄰的國家不能有相同顏色。做到這樣只需要4種顏色。
四色猜想最初于1852年提出，最初是英國的古德里在繪制英國地圖時(shí)抽象出來的問題，在和兄弟一起研究無果后，他向他的老師德摩根提了這個(gè)問題，但老師和他的數(shù)學(xué)家朋友也沒法解決這個(gè)小孩子都能聽懂的問題。1878年凱利向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了這個(gè)問題，從而使得該問題變得知名。
在幾乎同一年，在美國的律師肯普就給出了一個(gè)證明。他的思路是先證明所有地圖中都存在一小部分特殊的部分，只要這些特殊的部分都可以用四色填色，那么整張圖就可以用四色填色。然后他再證明這些特殊的部分都可以用四色填色。然而十一年后有人發(fā)現(xiàn)他給出的幾種特殊部分中，有一種并不能完全用肯普提供的方法填色?？掀兆詈笾皇亲C明了五色定理。
如此快對(duì)五色定理的解決讓人們相信四色定理十分簡單，紛紛開始嘗試。人們把肯普發(fā)現(xiàn)的特殊部分稱為“不可避免組”，開始繼續(xù)研究。然而隨著研究深入，人們發(fā)現(xiàn)不可避免組的數(shù)量越來越多，到最后無法通過人力去檢驗(yàn)和尋找。一百年以后，美國數(shù)學(xué)家阿佩爾和哈肯借助計(jì)算機(jī)，找到了全部的1963種不可避免組，并證明它們都是可以四色填色的。至此，四色猜想作為近代數(shù)學(xué)三大猜想（另外兩個(gè)是費(fèi)馬猜想和哥德巴赫猜想）中最早被證明的猜想，被稱為四色定理。
最為常見的偽證：平面上五個(gè)國家不可能兩兩相鄰
上圖的左邊就是在科普四色猜想時(shí)最為常用的地圖。如果我們把每個(gè)國家看成一個(gè)頂點(diǎn)，每個(gè)國家之間的相鄰關(guān)系用邊相連來表示，則我們可以把左邊的圖變成右邊的圖?？梢钥吹剑谟疫厛D中，沒有一條線是交叉的。我們把這種由頂點(diǎn)和邊構(gòu)成，每條邊兩端都有頂點(diǎn)且頂點(diǎn)不同，邊與邊之間不會(huì)交叉的圖暫且稱為平面圖（注：這是一個(gè)不嚴(yán)謹(jǐn)?shù)亩x）。很容易發(fā)現(xiàn)，所有的平面上的地圖都可以變成平面圖。四色猜想也就等價(jià)地變成了
給一個(gè)平面圖的頂點(diǎn)上色，要求每條邊的兩端的結(jié)點(diǎn)顏色不能相同，最多需要四種顏色。
右圖還有一種好處，就是它可以消去重復(fù)的邊，例如下圖。
如果在左邊的圖底下研究的話，紅色和藍(lán)色有兩條接壤邊界，而右圖中則只有一條邊就表達(dá)了相鄰關(guān)系。右圖更加抽象簡潔，因此我們之后會(huì)常用用右邊這種圖示。
扯遠(yuǎn)了，我們回頭看那張四個(gè)國家的圖。這張地圖非常典型，它是國家最少的需要四種顏色的地圖。在這張圖中，四個(gè)頂點(diǎn)兩兩相鄰（由一條邊相連）。我們將所有結(jié)點(diǎn)兩兩之間都有且僅有一條邊的圖稱為完全圖。n個(gè)結(jié)點(diǎn)的完全圖記作Kn。
然而，正因?yàn)樗^典型，很多人在開始研究這個(gè)問題時(shí)都會(huì)不由自主地被它限制住思路。由于這張圖中四個(gè)國家兩兩相鄰，于是很多人便認(rèn)為，只要證明平面上不存在五個(gè)頂點(diǎn)兩兩相鄰的情況，即證明K5不是平面圖，就能證明四色猜想。
K5不是平面圖這個(gè)證明非常簡單。但在此之前，我們先要證明一個(gè)引理：歐拉公式。不是那個(gè)指數(shù)虛數(shù)的，是多面體中頂點(diǎn)數(shù)加上面數(shù)減去棱數(shù)等于二那種公式。我們首先證明在平面圖中
V+F-E=2，其中V為頂點(diǎn)數(shù)，F(xiàn)為面數(shù)，E為邊數(shù)
這里的面是指由邊分割而成的聯(lián)通區(qū)域。我們可以在上面的平面圖中進(jìn)行驗(yàn)證：上圖有4個(gè)頂點(diǎn)，6條邊，4個(gè)面（注意，最外面的無限大區(qū)域也是一個(gè)面：顯然它是聯(lián)通的），符合上述公式。
那我們?cè)趺醋C明呢？我們可以對(duì)任何平面圖重復(fù)做如下操作：
如果平面圖中有一個(gè)頂點(diǎn)只與一條邊相連，那么我們可以刪去這條邊和這個(gè)頂點(diǎn)，這樣操作后。V減少1，F(xiàn)不變，E減少1，V+F-E不變。重復(fù)直至不存在這樣的頂點(diǎn)。
如果平面圖中有一條邊連接兩個(gè)頂點(diǎn)（注意由于我們是先做第一步的，這一步中的兩個(gè)頂點(diǎn)一定有其他邊相連），我們可以刪去這條邊，由這條邊分割的兩個(gè)面會(huì)變成一個(gè)面。這樣操作后，V不變，F(xiàn)減少1，E減少1，V+F-E不變。返回第一條判斷。
最終我們只會(huì)剩下一個(gè)頂點(diǎn)和一個(gè)以全平面為其內(nèi)容的面，V為1，F(xiàn)為1，E為0，V+F-E=2。而在上述操作中，等式左側(cè)的值永遠(yuǎn)不變。因此對(duì)任意平面圖，V+F-E=2。
歐拉公式證完了，接下來我們回到我們要證的東西：K5不可能是平面圖。
反證法，我們先假設(shè)K5是平面圖。那么，在K5中，V=5，E=5*4/2=10，因此F=2+E-V=2+10-5=7。平均每個(gè)面有2*10/7<3條邊，由平均數(shù)的意義，一定存在一個(gè)面的邊數(shù)小于等于兩條。而按照完全圖的定義，任意兩個(gè)頂點(diǎn)之間最多有一條邊，因此不可能存在只有兩條邊的面，而只有一條邊的面只可能出現(xiàn)在K2完全圖中，推出矛盾。假設(shè)錯(cuò)誤，因此K5不是平面圖。
很容易的，我們就把K5不是平面圖給證了出來。既然K5不是平面圖，那么也就沒有地圖能對(duì)應(yīng)K5，平面上也就不存在五個(gè)國家兩兩相鄰的情況。既然不存在五個(gè)國家兩兩相鄰，那么我們就不需要五種顏色。而既然已經(jīng)有必須要四種顏色地圖的例子，那四色猜想證完了呀！有什么問題？
問題就在于“如果一個(gè)地圖中不存在五個(gè)國家兩兩相鄰”并不能那么顯然地推出“那么地圖不需要五種顏色”。我們可以考慮這個(gè)推論的等價(jià)命題
如果一個(gè)平面圖任意五個(gè)頂點(diǎn)都不能構(gòu)成K5，那么這個(gè)平面圖不需要五種顏色去染色
單看這里，可能沒啥問題。但我們可以考慮一個(gè)更強(qiáng)的命題
如果一個(gè)圖需要五種顏色，那么這個(gè)圖存在5個(gè)頂點(diǎn)可以構(gòu)成K5
注意到在上述表述中，我把“平面”這個(gè)詞刪去了，也就是說，邊與邊之間可以交叉?；诖耍覀兛梢越o出如下圖。
可以看到，這張圖中邊有交叉。如果算一下歐拉公式你也會(huì)發(fā)現(xiàn)這不是平面圖。仔細(xì)觀察上圖的結(jié)構(gòu)，你會(huì)發(fā)現(xiàn)這張圖中有兩套共面的K4，這兩套K4又通過中間的紅色共頂點(diǎn)連接。因此，如果只能用四種顏色，為了滿足兩側(cè)的K4，中間的點(diǎn)和兩套K4最上方的點(diǎn)顏色必須一樣。而這兩套K4最上方的點(diǎn)又用一條邊相連，邊兩端頂點(diǎn)顏色相同，不符合上色要求。因此我們不得不引入第五種顏色。然而如果你仔細(xì)看的話，上圖并沒有哪五個(gè)點(diǎn)能構(gòu)成K5。上圖中沒有五個(gè)兩兩相鄰的點(diǎn)，但仍然需要五種顏色。
上面的反例是想說明什么呢？的確，我們的反例舉的是非平面圖的例子，對(duì)于證明或證偽四色猜想沒有任何幫助。然而，你能保證，一個(gè)沒有K5的平面圖，這個(gè)平面圖就一定不需要五種顏色去染色嗎？憑什么非平面圖會(huì)出現(xiàn)的反例，在平面圖上就不會(huì)出現(xiàn)？如果你能證明這樣的反例不可能出現(xiàn)在平面圖中，那這確實(shí)是證明了四色猜想。但問題是，你證明了嗎？
我們?cè)倏磧蓚€(gè)例子加深印象
顯然，這兩張圖都是平面圖。左邊的平面圖沒有K3，但是它需要三種顏色；右邊的平面圖沒有K4，但是它需要四種顏色。那么，你怎么能保證，一個(gè)沒有K5的平面圖，不需要五種顏色？
可能還有人不是很理解這段的反證法究竟是什么問題。我再詳細(xì)寫一下“反證法”的證明過程：
我們先假設(shè)存在一張平面圖都需要5種顏色染色，那么這張平面圖中一定存在一個(gè)由5個(gè)點(diǎn)構(gòu)成的完全圖K5。而K5不可能在平面圖中出現(xiàn)，因此假設(shè)錯(cuò)誤，平面圖不需要5種顏色去染色。
我們把上述證明中所有的5都換成n
我們先假設(shè)存在一張平面圖都需要n種顏色染色，那么這張平面圖中一定存在一個(gè)由n個(gè)點(diǎn)構(gòu)成的完全圖Kn。而Kn不可能在平面圖中出現(xiàn)，因此假設(shè)錯(cuò)誤，平面圖不需要n種顏色去染色。
我們會(huì)發(fā)現(xiàn)，證明的第一步在n=3、4的時(shí)候是不成立的，那為何在n=5的時(shí)候成立了呢？這需要給出詳細(xì)證明，而不是一個(gè)“顯然”就能過去的。如果不考慮證明過程的正確性而濫用反證法，就會(huì)鬧出如下笑話
如果1+1=2，那么太陽將從西邊升起。但太陽不可能從西邊升起，所以假設(shè)錯(cuò)誤，1+1≠2。
希望各位讀者好好理解這一節(jié)所講的內(nèi)容。根據(jù)我討論的經(jīng)驗(yàn)我發(fā)現(xiàn)很多人就是繞不過去這個(gè)坎，想不通這兩個(gè)命題實(shí)際上是不等價(jià)的。“圖沒有Kn”只是“圖不需要n種顏色”的必要條件，而非充要條件。由逆否命題等價(jià)性，“圖需要n種顏色”也只是“圖有Kn”的必要條件，而非充分條件。
此外還有一些其他的偽證思路，比如看上面4色無K4的反例圖，有人會(huì)發(fā)現(xiàn)它每個(gè)點(diǎn)都至少發(fā)出3條邊，因此可能認(rèn)為只要證明地圖中一定存在相鄰國家數(shù)小于4的國家，就能證明四色定理。這種證法在環(huán)面中是可以的，但是在平面中不成立。比如說我們可以對(duì)正十二面體球極投影，這樣得出來的一個(gè)12個(gè)頂點(diǎn)的平面圖，每個(gè)頂點(diǎn)都發(fā)出五條邊。這也是平面比環(huán)面難的一個(gè)原因。
還有的人可能看上面4色無K4和5色無K5，發(fā)現(xiàn)它們之中存在與K4和K5相似的結(jié)構(gòu)，因此給出猜想：只要一張圖能用四色染色，那么它一定不能通過刪邊、刪點(diǎn)和并點(diǎn)的變換變成K5及以上的。與前面兩個(gè)偽證不同，這個(gè)猜想是等價(jià)的，被稱為哈德威格猜想，
當(dāng)一張圖需要n種顏色才能染色時(shí)，Kn一定是該圖的圖子式
這里圖子式就是可以通過對(duì)原圖刪邊、刪頂點(diǎn)、融合一條邊相鄰的頂點(diǎn)獲得的圖。哈德威格本人證明了n=4的情況，可以用上面那張反例圖驗(yàn)證，K4盡管不是它的一個(gè)子圖，但確實(shí)是它的一個(gè)圖子式。1937年，Klaus Wagner證明了上述猜想在n=5時(shí)和四色定理是等價(jià)的。然而現(xiàn)在對(duì)n=5的證明都是從四色定理出發(fā)的，如果能繞過四色定理，那確實(shí)是一個(gè)完美的證明。
看點(diǎn)別的：四色問題推廣
那既然這不是證明，我們能怎么證明四色問題呢？很遺憾，由于四色問題現(xiàn)在依然處在計(jì)算機(jī)的統(tǒng)治之下，我并不能給出四色定理的詳細(xì)證明。不過對(duì)于一些簡單的問題，我們還是能證的。接下來，我們先看看四色問題朝其他方向的推廣，然后再證明四色定理的弱化版：六色定理和五色定理。
把一個(gè)問題推廣，一個(gè)方向就是改變問題的維數(shù)。一維曲線段很簡單，我們只需要2種顏色交替排布就能給所有國家上色?，F(xiàn)在，一維2種顏色，二維4種顏色（我們假定四色定理成立），那三維要幾種顏色呢？6種？8種？7種？都不是，答案是不存在這樣的最小值。
我們可以從下面這個(gè)簡單的模型中證明這一點(diǎn)?？赐曛?，讀者可以嘗試構(gòu)建一下自己的模型，留作習(xí)題。
我們將一些國家交替排布，于是我們可以得到上圖。
你也許要說，這樣交替排布只要兩種顏色就夠了！確實(shí)，但這里用不同顏色是為了下一步更為清楚。我們?cè)诘谝粋€(gè)國家（白色）的第一個(gè)方塊上向上延伸一格，然后向右覆蓋所有的其他國家。
這樣，第一個(gè)國家便與其他所有的國家相鄰。接下來，我們?cè)偃〉诙€(gè)國家（橙色）的第二個(gè)方塊向上延伸一格，然后向左右延伸覆蓋。
這個(gè)國家依然可以和所有國家相鄰！我們還可以對(duì)第三個(gè)、第四個(gè)……所有的國家都做一遍這個(gè)操作……
最終的結(jié)果就是所有的國家都會(huì)和所有其他國家相鄰！這就意味著所有國家都必須有一個(gè)不同的顏色！（還記得“沒有Kn”是“不用n種顏色”的必要條件嗎？否命題“有Kn”就是“要用n種及以上顏色”的充分條件了。）而盡管我們?cè)谏厦嬲故镜臅r(shí)候只使用了六個(gè)國家，但很顯然以上構(gòu)造過程中并沒有限制必須要六個(gè)國家。因此，對(duì)任意正整數(shù)n，我們都可以構(gòu)造出不能用n種顏色涂色的三維“地圖”！
升維不行，那我們只能研究二維問題了，二維問題也不光是平面，還有球面、甜甜圈面、莫比烏斯面等等。在這些面上，四色問題會(huì)有怎樣的結(jié)果呢？
（其實(shí)三維也不只有我們上面研究的那種樣子，還有比如說向二維球面一樣的三維空間：你往任意方向走都會(huì)在一定距離后回到最開始的位置。有人說其他種類的三維也不存在最少的顏色，但這方面我不太懂，不拓展了。）
先研究最簡單的球面。有人會(huì)認(rèn)為球面需要五色，比平面多一色。因?yàn)榍€段需要兩種顏色，而圓需要三種，多一種。那球面也應(yīng)當(dāng)比平面多一種，要五種。然而，這個(gè)答案是錯(cuò)誤的，因?yàn)榭梢院苋菀椎刈C明，球面和平面實(shí)際上是完全一樣的。
要做到這點(diǎn)，我們可以用一個(gè)叫做“球極投影”的變換。做法是將球放在平面上，將球最上方的點(diǎn)與球上其他點(diǎn)連線，連線與平面的交點(diǎn)即為投影點(diǎn)。這樣，除了北極點(diǎn)自身，其他所有點(diǎn)都和平面上的點(diǎn)一一對(duì)應(yīng)。
接下來我們旋轉(zhuǎn)球，讓最上方的點(diǎn)落在一個(gè)國家的內(nèi)部，這樣，我們就可以獲得一張平面圖，這張圖的外圍是一個(gè)無限大的國家。
然而如果你把它轉(zhuǎn)成平面圖，你會(huì)發(fā)現(xiàn)這依然是一個(gè)有限的圖！無限大小的國家并沒有對(duì)應(yīng)成無限多的頂點(diǎn)?；蛘撸阋部梢岳斫獬?，上面那張無限地圖和下面這張有限地圖其實(shí)是完全等價(jià)的。
也就是說，只要平面四色能畫完，球面四色一定能畫完；平面畫不完，球面也一定畫不完。這也說明，隨隨便便把其他維度的結(jié)果抄過來并不總能給出正確的結(jié)果。
球面是四個(gè)，其他面呢？我們先考慮甜甜圈。甜甜圈面（環(huán)面）和球面一樣，是一個(gè)可定向閉曲面。也就是說，它有“里面”和“外面”，而且沒有邊界。我們之前證了平面上的歐拉公式，球面上的我們可以用球極投影證明球面上的公式是完全一樣的，也就是常用的多面體的歐拉公式。但環(huán)面中間有個(gè)洞，這就導(dǎo)致我們之前用到的歐拉公式并不能直接用在環(huán)面上。我們需要把公式改造一下，變成V+F-E=0。如果曲面再多一個(gè)洞，那右邊再減2。
接下來怎么證？我們仿照平面地圖的方法，將它轉(zhuǎn)成一個(gè)圖。如果轉(zhuǎn)成的圖中有面只有兩條以下邊，這個(gè)面只能是整個(gè)環(huán)面，這些情況顯然可以用七色填色。如果有只有一條邊連接的頂點(diǎn)，那只要剩下的圖可以七色填色，加上這個(gè)頂點(diǎn)依然可以七色填色，因此我們可以把所有這樣的頂點(diǎn)刪去。對(duì)于剩下的情況，面的邊數(shù)至少為3，每條邊的兩側(cè)都是不同的面，因此3F≤2E，由歐拉公式推知，3V≥E，2*E/V≤6。也就是說平均每個(gè)頂點(diǎn)發(fā)出的邊數(shù)小于等于6，因此必然存在發(fā)出邊數(shù)小于等于6的頂點(diǎn)。
對(duì)于n個(gè)頂點(diǎn)的圖，我們找到一個(gè)邊數(shù)小于等于6的頂點(diǎn)，刪去該頂點(diǎn)及與其相鄰的邊，如果剩下的n-1個(gè)頂點(diǎn)的圖可以用七色填色，原來的圖也可以。而這個(gè)新的n個(gè)頂點(diǎn)的圖也有一個(gè)邊數(shù)小于等于6的點(diǎn)，我們重復(fù)這樣的操作，最后只剩下小于等于7個(gè)頂點(diǎn)時(shí)一定可以用七色涂色。因此任意環(huán)上的地圖都可以用7色涂色。
接下來只要我們能找到一張必須要7種顏色涂色的地圖，就能證明環(huán)面七色定理。幸運(yùn)的是，人們找到了它。
其他曲面也有類似定理，例如在莫比烏斯帶上需要6種顏色。
在“推廣”這章的最后，我們來看一下現(xiàn)實(shí)世界中的地圖，考慮一下飛地問題。飛地就是地圖上盡管沒有相鄰，但是需要是有相同顏色的區(qū)域。按這個(gè)定義來講，飛地其實(shí)遠(yuǎn)比想象的要多。比如現(xiàn)實(shí)世界中，所有的湖泊都可以看作海洋的“飛地”。
我們接下來給出一種構(gòu)造，以證明當(dāng)?shù)貓D具有飛地時(shí)，顏色就沒有上限了。比如我們考慮一個(gè)已經(jīng)需要n種顏色的地圖，我們往這張圖上添加一個(gè)新國家，這個(gè)國家在其他每個(gè)國家中都有一塊飛地。這樣這個(gè)國家就必須要一種新的顏色，不能用原來的n種顏色。因此需要的顏色無上限。
因此當(dāng)有飛地存在時(shí)，四色定理是不成立的，這也是為什么現(xiàn)實(shí)世界的地圖繪圖時(shí)通常不會(huì)特別去應(yīng)用四色定理。
四色定理弱化版：六色定理和五色定理
推廣推完了，我們接下來嘗試一下接近四色定理，證明六色定理和五色定理。
還記得我們之前的環(huán)面七色定理嗎？我們可以把這個(gè)證明過程照搬到平面上，從歐拉公式得到6>2E/V，這樣一定存在一個(gè)頂點(diǎn)只發(fā)出小于等于5條邊。因此類比在環(huán)面上的證明可知6種顏色一定能繪圖。六色定理就這樣證明了。
五色定理需要一點(diǎn)技巧，我們這里介紹肯普的證明。首先，對(duì)于頂點(diǎn)數(shù)小于等于5的平面圖，一定可以用五種顏色繪圖。接下來，考慮頂點(diǎn)數(shù)大于6個(gè)的情況，找到發(fā)出邊數(shù)最少的頂點(diǎn)，
如果這個(gè)點(diǎn)發(fā)出的邊數(shù)小于等于4，那么很顯然這個(gè)頂點(diǎn)可以不考慮，其他點(diǎn)如何用五種顏色涂色并不影響這個(gè)點(diǎn)，因?yàn)檫@個(gè)點(diǎn)只要取與它相鄰顏色不同的顏色即可。
如果有發(fā)出了5條邊，我們先刪去這個(gè)頂點(diǎn)，然后對(duì)剩下的圖用5種顏色涂色，涂完以后再把這個(gè)點(diǎn)加回來看它應(yīng)該涂什么顏色。如果相鄰的五個(gè)頂點(diǎn)有相同的顏色，那么該頂點(diǎn)不能選擇的顏色數(shù)就小于4，我們依然可以找到一種顏色給它填上。
真正的難點(diǎn)在于處理相鄰5個(gè)頂點(diǎn)顏色都不相同的情況。這時(shí)你就沒法用舊顏色去填充了。但我們接下來要證明，我們可以通過修改原本的填色方式，使得這5個(gè)相鄰頂點(diǎn)中出現(xiàn)顏色相同的頂點(diǎn)。
這里我們需要引入一個(gè)肯普在他的證明中的概念：肯普鏈。肯普鏈就是只有兩種給定顏色頂點(diǎn)構(gòu)成的極大聯(lián)通子圖。就像下圖中，圈出來的黃綠色可以組成一條肯普鏈，紅藍(lán)也可以組成一條2個(gè)頂點(diǎn)的肯普鏈，紅綠則有一條3個(gè)頂點(diǎn)的和一條1個(gè)頂點(diǎn)的（最上方的那個(gè)綠色頂點(diǎn)）。
由于肯普鏈?zhǔn)前阉新?lián)通的兩種顏色的頂點(diǎn)給包括了進(jìn)去，因此與肯普鏈相鄰的點(diǎn)不會(huì)有肯普鏈上的顏色。因此我們可以做出反色操作：設(shè)肯普鏈上有顏色A和顏色B，我們把鏈上所有顏色為A顏色的頂點(diǎn)換成B顏色，B顏色的頂點(diǎn)換成A顏色。這樣的圖依然不會(huì)產(chǎn)生矛盾。就像下圖所示的那樣。
基于此，我們就可以給出證明，我們考慮下圖的模型
我們?nèi)我膺x擇兩個(gè)間隔一格的顏色，比如這里我們選擇藍(lán)色和橙色，找到連接這兩個(gè)頂點(diǎn)所屬的藍(lán)橙肯普鏈。如果像下圖一樣，這是兩條不同的，那我們就可以把其中一條肯普鏈反色，這樣這兩個(gè)頂點(diǎn)的顏色就完全相同了。
但如果這兩個(gè)頂點(diǎn)屬于同一條肯普鏈，那么它就會(huì)把紅色和黃色、綠色分割開來，我們可以在紅色結(jié)點(diǎn)上尋找紅黃肯普鏈或紅綠肯普鏈，將其反色，這樣又造出了兩個(gè)相同顏色的結(jié)點(diǎn)。
這樣我們就證完了五色定理。
四色定理的遺憾：計(jì)算機(jī)證明
上面這套證法是肯普的四色定理偽證被發(fā)現(xiàn)錯(cuò)誤的附帶產(chǎn)物。肯普本人也是用肯普鏈去證明四色定理，然而人們檢查他的證明過程后發(fā)現(xiàn)，對(duì)于有4個(gè)鄰國的證明，肯普的證明完全正確，但有5個(gè)的證明并不嚴(yán)密。由此開啟了數(shù)學(xué)家們百年打補(bǔ)丁的奮斗歷程。
很明顯，只要一張地圖有一小塊區(qū)域不能用四色填色，整張地圖就不能用四色填色。因此，人們就開始尋找這個(gè)最小的區(qū)域以證偽四色猜想，或者證明平面圖上不可能存在這樣的區(qū)域。
但是，平面有無限種可能的劃分，我們應(yīng)當(dāng)怎么去研究這無限多種呢？人們開始想盡一切辦法去歸類可能的地圖。比如像本文最開始把地圖變成平面圖，就把一大堆實(shí)質(zhì)相同，但看起來不同的地圖歸為一類。再比如，因?yàn)橛?個(gè)鄰國的證明是正確的，因此可能舉出的反例中最小的圖必然不存在發(fā)出邊數(shù)小于4條以下的頂點(diǎn)，因此研究的平面圖必須保證圖中所有頂點(diǎn)都至少發(fā)出五條邊，否則那個(gè)頂點(diǎn)便會(huì)被刪去。再比如，平面圖中所有的面都應(yīng)該只有三條邊，因?yàn)槿绻幸粋€(gè)面有四條邊，我們就能把它割成兩個(gè)三條邊的面，后者多了一個(gè)相鄰關(guān)系，約束關(guān)系比前者更強(qiáng)。但即使做了這么多剪枝，要研究的圖形還是無限多的。于是人們便開始找這些圖中有沒有一些特定的關(guān)系。
肯普的證明表明，一張平面圖中，一定存在一個(gè)邊數(shù)小于等于5的頂點(diǎn)，這再任何平面圖中都不可避免，肯普也根據(jù)這個(gè)不可避免的頂點(diǎn)將所有的平面圖分了類。后來人們將這種不可避免的部分稱為“不可避免組”。如果能找到所有的不可避免組，就能按照各組的方式去約化圖形。這樣就能化無限為有限。
1970年，德國數(shù)學(xué)家Heesch在證明過程中引入了放電法。核心就是把平面圖看成電路圖，然后根據(jù)歐拉公式計(jì)算出的發(fā)出不同數(shù)量的邊的頂點(diǎn)的比例，在每個(gè)頂點(diǎn)上放上相應(yīng)的正電荷，讓電荷開始流動(dòng)。如果推出矛盾，比如流動(dòng)前后電荷不守恒，那么這張圖就不成立。在大西洋對(duì)岸，1972年，數(shù)學(xué)家Appel了解到這種解決方法后決定使用計(jì)算機(jī)進(jìn)行處理。1976年，在對(duì)Heesch的程序和證明方法進(jìn)行大量改進(jìn)后，Appel等人發(fā)現(xiàn)不可避免組總共只有1936個(gè)（我理解的其實(shí)已經(jīng)約化很多了，畢竟Heesch列了8900多種）。然后他們便對(duì)這所有的1936個(gè)組分類討論，用計(jì)算機(jī)程序程序進(jìn)行檢查，在1200個(gè)小時(shí)的運(yùn)算后，1936種情況全部檢驗(yàn)成功，四色定理終于得證。
盡管證明了，但大家依然抱著非常謹(jǐn)慎的態(tài)度。因?yàn)榍败囍b實(shí)在過多，讓大家難以相信這個(gè)定理就這么被證明了。不斷有人指出程序中的漏洞，證明團(tuán)隊(duì)也不斷地打補(bǔ)丁。在經(jīng)歷漫長的修正和驗(yàn)證后，程序和證明最終被發(fā)現(xiàn)無可挑剔，人們也接受了四色猜想作為一個(gè)定理存在。
但1963種依然過多，原本的證明團(tuán)隊(duì)后來把不可避免組的數(shù)量約化到了1482種。1996年，Robertson等人在Appel的基礎(chǔ)上將不可避免組的數(shù)量約化到了633種，并且還優(yōu)化了算法，大大降低了時(shí)間復(fù)雜度。
四色定理最終被證明了，但數(shù)學(xué)家們一開始卻高興不起來。因?yàn)檫@種證明充其量就是大力出奇跡，一點(diǎn)沒有數(shù)學(xué)的簡潔之美。更重要的是，這套證明并沒有給其他的問題提供太多幫助。安德魯懷爾斯在證明近代數(shù)學(xué)三大猜想的另一個(gè)猜想，費(fèi)馬大定理的時(shí)候做了許多創(chuàng)新的工作，并運(yùn)用了朗蘭茲綱領(lǐng)中的思想，架設(shè)起了數(shù)學(xué)不同領(lǐng)域之間的橋梁。而四色定理就沒有如此多的成果。數(shù)學(xué)家的解決問題的最終目的不是解決問題，而是在解決問題中創(chuàng)造新的工具以解決其他問題。所以在最開始，這一證明不受很多數(shù)學(xué)家待見。直到現(xiàn)在，依然有部分?jǐn)?shù)學(xué)家抱著“我可以接受這個(gè)證明是正確的，但我絕對(duì)不接受這個(gè)證明”的心理，嘗試給出一些更“數(shù)學(xué)”的證明。
然而，作為第一個(gè)使用計(jì)算機(jī)的數(shù)學(xué)證明，四色定理的證明成功打破了數(shù)學(xué)家們對(duì)計(jì)算機(jī)的抗拒心理，現(xiàn)在，越來越多的數(shù)學(xué)定理的證明過程開始基于計(jì)算機(jī)。這也可以算是四色定理的一項(xiàng)成果吧。
