四色定理

最近讀到一個可愛的東西叫四色定理，它曾經因為〈嫌疑犯X的獻身〉熱鬧過一陣子。這是個有關地圖上色的定理，簡單描述如下：「任何一個無飛地的地圖只需要用四種顏色就可以全部上色，而且每一個相鄰地區的顏色都不一樣。」
　　
飛地是地理名詞，可以分成兩種。一種是國中有國，類似甜甜圈那種樣子。另一種是一個國家的國土被拆成不相連的多個部分，而且被其他國家隔開。繪製地圖時我們通常要求同一國家的領土必須使用同一個顏色，所以飛地的存在會讓著色問題變得複雜。但如果不考慮飛地，四色問題其實就只是一個著色本問題而已。
　　
四色問題最早由Guthrie在1852年發現，後來成為一個數學猜想並傳到De Morgan耳裡。此後De Morgan花了很多心力在研究和宣傳四色問題上面。
　　
這個問題一開始有很長一段時間不受到數學界的重視，投入的人力有限。這個領域的早期工作總結在Kempe的證明上，為後來的研究定下基礎。他採用的是數學歸納法，思路如下：
　　
一、 因為我們有4個顏色可以用，所以當一個地圖的國家數目不超過4個，一定可以讓所有國家都畫上不同顏色；四色定理顯然成立。
　　
二、 對於任何一張包含n個國家的地圖，假設四色定理成立。
　　
三、考慮一張隨機地圖，上面有n+1個國家。設法證明這張地圖依然可以只用4個顏色為所有國家上色，而且符合四色定理。
　　
四、只要第三點能夠做到，根據數學歸納法，我們可以結論說四色定理在任意地圖都成立。
　　
顯然真正要處理的只有第三點，步驟如下：
　　
(i)、設法證明任意地圖必定包含一個國家叫做 Least，它的鄰國最多只有5個。
　　
(ii)、Least的鄰國如果在3個以下，利用併吞法證明四色定理在這張n+1國的地圖中成立。
　　
(iii)、Least的鄰國如果是4個，利用併吞法證明四色定理在這張n+1國的地圖中成立。
　　
(iv)、Least的鄰國如果是5個，利用併吞法證明四色定理在這張n+1國的地圖中成立。
　　
(v)、以上4點若能做到，則第三點得證，於是四色定理得證。
　　
我不打算把這篇文章寫得太長，所以不在這裡解釋第(i)點怎麼證明。以下介紹第(ii)點和第(iii)點的證明，這是我認為格外有趣的部分。
　　
關於第(ii)點，也就是Least有3個鄰國的情況：考慮圖一，這是一張n+1國的地圖。首先讓A國併吞Least，於是這張地圖只剩下n個國家。根據上述第二點，現在這張地圖一定可以用4種顏色為所有國家上色。假定著色之後如圖二，英文字母旁邊的數字表示顏色編號。
　　
接著讓Least復國，這時整個地圖的國家總數回到n+1。因為Least只有3個鄰國，這3個鄰國所使用的顏色最多3種，所以Least一定可以用第4種顏色來上色；如圖三。現在這張n+1國的地圖就完成著色了。
　　
當然，如果Least的鄰國數比3還少，用同樣的手法來上色顯然是沒問題的，故第(ii)點得證。
　　
現在說明第(iii)點，Least有4個鄰國的情況。這個情況是Kempe整個思路的重心，稍微複雜。
　　
首先考慮一個n+1國的地圖，如圖四。一樣先讓A國併吞Least，剩下n個國家後再利用第二點的假設把整張地圖上色。
　　
這會有好幾種可能的狀況，我們只需要考慮A、B、C、D等4國顏色都不一樣的狀況。因為，如果這4國只用了3種顏色、或比3種顏色還少，那麼我們只要讓Least復國後直接塗上沒用到的顏色就可以了。
　　
所以只要討論4國不同色的情況，如圖五，這是一張n個國家的地圖而且全部上色了。Kempe想到一種換色技巧來減少這4個國家所使用的顏色，比如把A國換成第3色，和C國一樣。
　　
因為四色定理要求相鄰的國家不能用同樣的顏色，所以，如果E國不是用第3色，那麼A國換色不會有問題。但如果E國也是第3色，當我們把A國換成第3色時，要把E國換成第1色；再進一步，如果不幸的F也是第1色，則必須再把F換成第3色，以此類推；也就是所有顏色衝突的國家都要換色，直到顏色沒有衝突。
　　
現在把A國換成第3色，而且把顏色有衝突的國家照上面說的方法一併換色，最後得到圖六。這時我們發現A、B、C、D等4國只用了3個顏色，於是可以讓Least復國，整張地圖的國家總數回到n+1。然後給Least填上第1色，如圖七，便得到一張滿足四色定理的地圖了。
　　
可是有一種極特殊的狀況是：當A國換成第3色時，因為鄰國顏色衝突必須一路換色，換、換、換……換到後來竟然連C國都要換色了；也就是C國換成第1色，如圖八。這時候看起來Least的鄰國還是用了4個顏色，還不能讓Least復國，要進一步處理。
　　
這時把D換成第2色，也就是和B同色，這樣做也是希望夠減少顏色的數目。當然，如同上面的換色方法，所有因此產生顏色衝突的國家都要換色。這個動作必定可以做到，而且D換色一定不會影響到B，也就是說不會因為連鎖反應導致B也要換色。原因是圖八有一條Kempe Chain。
　　
在圖八的狀況中可以發現，A國換色導致了一連串的換色效應。如果從A國出發沿著有換色的國家一路前進，最後會走到C國，因此形成的藍色路徑就叫Kempe Chain。
　　
進一步可以看出，這些換色的國家不僅兩兩相鄰，而且不是第1色就是第3色。所以當我們把D換成第2色，不管怎麼換，最後一定不會超出Kempe Chain的封鎖。因為Kempe Chain上的國家沒有一個使用第2色，絕對不會有顏色衝突。
　　
把D換成第2色之後，A、B、C、D便只用了3種顏色，這時可以讓Least復國並填上第4色。最後我們便得到一張滿足四色定理的n+1國地圖。
　　
換色技巧和Kempe Chain的觀念是這個證明的兩個妙手，非常精彩。到這裡我們已經把第(iii)點證明完畢。
　　
關於Least有5個鄰國的情況，Kempe也用同樣的手法來處理，並且宣稱四色定理的證明已經完成。可是後來Heawood指出這個方法在5個鄰國的情況中並不是永遠成功，而且他還給出一個反例；這宣告了Kempe的失敗。就這樣，四色問題成為數學界懸而未決的問題之一，經過漫長的努力都無法攻破。
　　
一直到1976年，Appel與Haken利用電腦解決了龐大的檢驗計算，證明四色定理成立。這是第一個必須使用電腦才能證明的數學問題，存在許多爭議，像是「電腦計算能不能等同傳統證明？」不過這些哲學論戰是另一個故事了。
　　
時至今日，有人已經接受電腦作為證明的工具，也有人還是希望找到一個傳統的證明，就像小說裡的石神。Kempe的工作儘管沒有成功，仍然發揮了承先啟後的作用，而換色技巧和Kempe Chain這兩個靈感也將流傳下去。無論電腦的計算能力如何強大，那道靈感閃現的光芒始終是數學證明最迷人的地方。