五色定理

1879 年英國律師出身的數學家肯普在美國數學雜誌上發表一篇論文。他聲稱自己已經解決了四色問題。並因其對數學的貢獻最終被封為爵士。他用歸謬法證明“四色猜想”，提出了“不可避免集”的構形和構形的可約性。他用肯普鏈的方法證明，如圖1，如果一個頂點 V與 5 個其他用四種顏色着色的點鄰接，那麼總能多出諸顏色之一來給 V着色，他用了鄰接點交錯着色的道路（肯普鏈），交換這些道路上的顏色，以便空出一種顏色給 V。

1890 年英國著名數學家希伍德發表了一篇論文。這篇論文震動了數學界。他舉出了“有名反例”，如圖 2。在肯普看上去解決了這個問題之後 10 年，希伍德用這個“反例”揭示肯普證明四色問題有重大缺陷，並證明反例是 5- 色的。從而希伍德指出：“如果‘四’換成‘五’這個猜想就對了”。他否定了肯普“四色猜想”的證明。肯普失敗了。同時希伍德證明建立了“五色定理”。

四色定理又稱四色猜想、四色問題，四色問題的內容是“任何一張地圖只用四種顏色就能使具有共同邊界的國家着上不同的顏色。”也就是説在不引起混淆的情況下一張地圖只需四種顏色來標記就行。

用數學語言表示即“將平面任意地細分為不相重疊的區域，每一個區域總可以用1234這四個數字之一來標記而不會使相鄰的兩個區域得到相同的數字。”這裏所指的相鄰區域是指有一整段邊界是公共的。如果兩個區域只相遇於一點或有限多點就不叫相鄰的。因為用相同的顏色給它們着色不會引起混淆。

1852年，畢業於倫敦大學的格斯里（Francis Guthrie）來到一家科研單位搞地圖着色工作時，發現每幅地圖都可以只用四種顏色着色。這個現象能不能從數學上加以嚴格證明呢？他和他正在讀大學的弟弟決心試一試，但是稿紙已經堆了一大疊，研究工作卻是沒有任何進展 ^[1]  。

1852年10月23日，他的弟弟就這個問題的證明請教了他的老師、著名數學家德·摩爾根，摩爾根也沒有能找到解決這個問題的途徑，於是寫信向自己的好友、著名數學家哈密頓爵士請教，但直到1865年哈密頓逝世為止，問題也沒有能夠解決。

1872年，英國當時最著名的數學家凱利正式向倫敦數學學會提出了這個問題，於是四色猜想成了世界數學界關注的問題，世界上許多一流的數學家都紛紛參加了四色猜想的大會戰。

從此，這個問題在一些人中間傳來傳去，當時，三等分角和化圓為方問題已在社會上“臭名昭著”，而“四色瘟疫”又悄悄地傳播開來了。

1878～1880年兩年間，著名的律師兼數學家肯普(Alfred Kempe)和泰勒(Peter Guthrie Tait)兩人分別提交了證明四色猜想的論文，宣佈證明了四色定理。

大家都認為四色猜想從此也就解決了，但其實肯普並沒有證明四色問題。11年後，即1890年，在牛津大學就讀的年僅29歲的赫伍德以自己的精確計算指出了肯普在證明上的漏洞。他指出肯普説沒有極小五色地圖能有一國具有五個鄰國的理由有破綻。不久泰勒的證明也被人們否定了。人們發現他們實際上證明了一個較弱的命題——五色定理。就是説對地圖着色，用五種顏色就夠了。

不過，讓數學家感到欣慰的是，郝伍德沒有徹底否定肯普論文的價值，運用肯普發明的方法，郝伍德證明了較弱的五色定理。這等於打了肯普一記悶棍，又將其表揚一番，總的來説是貶大於褒。真不知可憐的肯普律師是什麼心情。 追根究底是數學家的本性。一方面，五種顏色已足夠，另一方面，確實有例子表明三種顏色不夠。那麼四種顏色到底夠不夠呢？這就像一個淘金者，明明知道某處有許多金礦，結果卻只挖出一塊銀子，你説他願意就這樣回去嗎？

肯普是用歸謬法來證明的，大意是如果有一張正規的五色地圖，就會存在一張國數最少的“極小正規五色地圖”，如果極小正規五色地圖中有一個國家的鄰國數少於六個，就會存在一張國數較少的正規地圖仍為五色的，這樣一來就不會有極小五色地圖的國數，也就不存在正規五色地圖了。這樣肯普就認為他已經證明了“四色問題”，但是後來人們發現他錯了。

不過肯普的證明闡明瞭兩個重要的概念，對以後問題的解決提供了途徑。第一個概念是“構形”。他證明了在每一張正規地圖中至少有一國具有兩個、三個、四個或五個鄰國，不存在每個國家都有六個或更多個鄰國的正規地圖，也就是説，由兩個鄰國，三個鄰國、四個或五個鄰國組成的一組“構形”是不可避免的，每張地圖至少含有這四種構形中的一個。

肯普提出的另一個概念是“可約”性。“可約”這個詞的使用是來自肯普的論證。他證明了只要五色地圖中有一國具有四個鄰國，就會有國數減少的五色地圖。自從引入“構形”，“可約”概念後，逐步發展了檢查構形以決定是否可約的一些標準方法，能夠尋求可約構形的不可避免組，是證明“四色問題”的重要依據。但要證明大的構形可約，需要檢查大量的細節，這是相當複雜的。

人們發現四色問題出人意料地異常困難，曾經有許多人發表四色問題的證明或反例，但都被證實是錯誤的。後來，越來越多的數學家雖然對此絞盡腦汁，但一無所獲。於是，人們開始認識到，這個貌似容易的題目，其實是一個可與費馬猜想相媲美的難題。　

進入20世紀以來，科學家們對四色猜想的證明基本上是按照肯普的想法在進行。

1913年，美國著名數學家、哈佛大學的伯克霍夫利用肯普的想法，結合自己新的設想；證明了某些大的構形可約。後來美國數學家富蘭克林於1939年證明了22國以下的地圖都可以用四色着色。

1950年，温恩從22國推進到35國。

1960年，有人又證明了39國以下的地圖可以只用四種顏色着色；隨後又推進到了50國。看來這種推進仍然十分緩慢。

高速數字計算機的發明，促使更多數學家對“四色問題”的研究。電子計算機問世以後，由於演算速度迅速提高，加之人機對話的出現，大大加快了對四色猜想證明的進程。就在1976年6月，在美國伊利諾斯大學的兩台不同的電子計算機上，用了1200個小時，作了100億個判斷，結果沒有一張地圖是需要五色的，最終證明了四色定理，轟動了世界。

第一個計算機解是由美國數學家Appel和Haken與運用計算機的專家Kock三人合作的成果 ^[2]  。這是一百多年來吸引許多數學家與數學愛好者的大事，當兩位數學家將他們的研究成果發表的時候，當地的郵局在當天發出的所有郵件上都加蓋了“四色足夠”的特製郵戳，以慶祝這一難題獲得解決。