★置頂zzllrr小樂公眾號（主頁右上角）數(shù)學(xué)科普不迷路！

今年是四色定理誕生50周年。四色問題探討的是：在平面或球面上繪制的任意地圖，是否僅需四種顏色就能對所有區(qū)域進(jìn)行著色，且使任何共享一條公共邊界線的兩個區(qū)域顏色不同。該問題于1852年由弗朗西斯·格思里（Francis Guthrie）首次提出，最終在1976年由肯尼斯·阿佩爾（Kenneth Appel）和沃爾夫?qū)す希╓olfgang Haken）解決，此后被正式稱為四色定理。

作者：羅賓·威爾遜（Robin Wilson）《美國數(shù)學(xué)會通告》

AMS Notices

2026-3

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2026-2-25

作者簡介

羅賓·威爾遜（Robin Wilson），英國開放大學(xué)純數(shù)學(xué)榮譽(yù)退休教授、倫敦格雷沙姆學(xué)院幾何學(xué)榮譽(yù)退休教授，同時曾任牛津大學(xué)基布爾學(xué)院研究員。

為紀(jì)念這一定理誕生50周年，本文將回溯其證明歷程，重點(diǎn)聚焦于參與其中的關(guān)鍵人物。

1. 奧古斯塔斯·德摩根（Augustus De Morgan）

圖1 奧古斯塔斯·德摩根（1806-1871）

奧古斯塔斯·德摩根是新成立的倫敦大學(xué)學(xué)院的首位數(shù)學(xué)教授。他在數(shù)學(xué)、邏輯學(xué)和哲學(xué)領(lǐng)域貢獻(xiàn)卓著，以集合論中的“德摩根定律”（De Morgan’s laws）聞名于世。同時，他也是一位多產(chǎn)的通俗數(shù)學(xué)作家，其著作《悖論集錦》

Budget of Paradoxes

收錄了他在當(dāng)時的文學(xué)與科學(xué)期刊《雅典娜神廟》

The Athenaeum

上發(fā)表的大量文章，于1872年出版。1865年，他當(dāng)選為倫敦數(shù)學(xué)會首任主席。

多年來，德摩根與愛爾蘭數(shù)學(xué)家威廉·羅恩·哈密頓（William Rowan Hamilton，又譯漢密爾頓）爵士保持通信，分享彼此的近況、數(shù)學(xué)界的趣聞以及家庭瑣事。1852年10月23日，他在給哈密頓的信中寫道：

“今天我的一名學(xué)生向我詢問一個事實的緣由，而我此前并不知道這是一個事實——至今也仍未弄清。他說，若將一個圖形任意分割，給各個部分著色，使得任何具有公共邊界線的部分顏色不同，那么最多只需四種顏色……我想知道，是否能構(gòu)造出需要五種或更多顏色的情況……”

作為需要四種顏色的地圖示例，德摩根繪制了四個兩兩相鄰的區(qū)域。

后來證實，這位“學(xué)生”是弗雷德里克·格思里（Frederick Guthrie），他后來成為物理學(xué)家，也是倫敦物理學(xué)會的創(chuàng)始人。1880年，他在《愛丁堡皇家學(xué)會會刊》

Proceedings of Edinburgh’s Royal Society

上發(fā)表短文，將這一問題歸功于他的兄長弗朗西斯·格思里——弗朗西斯曾是德摩根的學(xué)生，在為英格蘭地圖著色時提出了“四種顏色是否足夠為所有地圖著色”的疑問。弗朗西斯·格思里最終成為南非的數(shù)學(xué)教授，同時也是公認(rèn)的植物學(xué)專家；多種植物以他的名字命名，包括石楠花 Erica Guthriei。盡管他此后再未深入研究這一問題，但四色問題有時仍被稱為“格思里問題”（Guthrie’s problem）。

圖2 弗朗西斯·格思里（1831-1899）

四色問題也曾被錯誤地歸功于德國數(shù)學(xué)家兼天文學(xué)家奧古斯特·莫比烏斯（August M?bius）。1840年，莫比烏斯給學(xué)生布置了一道題目：一位垂死的國王將土地遺贈給五個兒子，要求他們將土地分成五個部分，每個部分都與其他四個部分相鄰。如果在平面上存在這樣五個兩兩相鄰的區(qū)域，那么繪制此類地圖就需要五種顏色，但證明這種分割不存在，并不能直接證明四色定理——這一誤解在該問題的歷史上曾多次出現(xiàn)。

德摩根被這個挑戰(zhàn)深深吸引，他向親友和同事詢問是否有人已找到解決方案，但始終沒有得到明確答案。從一開始，他就錯誤地認(rèn)為，證明的關(guān)鍵在于：若地圖中存在四個兩兩相鄰的區(qū)域，則其中一個區(qū)域必然被另外三個區(qū)域包圍。當(dāng)他向四元數(shù)代數(shù)體系的發(fā)明者哈密頓提及這一想法時，得到了簡潔卻恰當(dāng)?shù)幕貞?yīng)：“我不太可能很快嘗試你的‘顏色四元數(shù)’問題?！?/p>

四色問題最早的印刷描述出現(xiàn)在1854年，《雅典娜神廟》期刊的一個專欄中刊登了題為《地圖著色》

Tinting Maps

的段落，署名“F. G.”。這可能是弗雷德里克·格思里、弗朗西斯·格思里所寫，也可能出自當(dāng)時正尋求加入倫敦雅典娜神廟俱樂部的地理學(xué)家兼博學(xué)家弗朗西斯·高爾頓（Francis Galton）之手。

1860年，該期刊再次刊登了一篇由德摩根撰寫的匿名書評，提及了這一問題。正是由于這篇書評，四色問題傳入美國，引起了查爾斯·桑德斯·皮爾士（Charles Sanders Peirce）的關(guān)注。當(dāng)時皮爾士正在哈佛大學(xué)求學(xué)，他的父親本杰明·皮爾士（Benjamin Peirce）是當(dāng)時美國最杰出的數(shù)學(xué)家；后來，查爾斯·皮爾士成為著名的邏輯學(xué)家和哲學(xué)家。這位年輕的學(xué)者曾向哈佛數(shù)學(xué)會提交過一個解決方案，但具體內(nèi)容已無從考證。

2. 阿瑟·凱萊（Arthur Cayley）

德摩根于1871年去世，至死都未能知曉四色定理是否成立，這一問題似乎也隨之被淡忘。但七年后，在倫敦數(shù)學(xué)會的一次會議上，劍橋數(shù)學(xué)家阿瑟·凱萊（Arthur Cayley）重新提出了這一問題，使其重獲關(guān)注。

圖3 阿瑟·凱萊（1821-1895）

阿瑟·凱萊出生于倫敦，但早年隨經(jīng)商的父親在俄羅斯生活?；氐接螅趥惗亟邮芙逃?7歲時進(jìn)入劍橋大學(xué)三一學(xué)院。1840年以優(yōu)異成績畢業(yè)后，他被任命為學(xué)院研究員，但由于需要接受英國國教的圣職，他于1844年離開劍橋，在倫敦的律師學(xué)院擔(dān)任了19年的成功律師。在此期間，他撰寫了超過300篇數(shù)學(xué)論文，并結(jié)識了好友兼合作者詹姆斯·約瑟夫·西爾維斯特（James Joseph Sylvester），兩人共同開創(chuàng)了代數(shù)學(xué)的新領(lǐng)域——不變量理論（invariant theory）。1863年，他回到劍橋，擔(dān)任首任薩德勒（Sadleirian）純粹數(shù)學(xué)教授，并在此職位上度過余生。

繼德摩根之后，西爾維斯特和凱萊先后擔(dān)任倫敦數(shù)學(xué)會主席。1870年代，凱萊開始涉足化學(xué)分子計數(shù)領(lǐng)域，而西爾維斯特則探索分子與代數(shù)不變量之間的潛在聯(lián)系，并于1878年引入了“圖”（graph）一詞（即圖論意義上的“圖”）。

1875年，五年前從伍爾維奇皇家軍事學(xué)院退休的西爾維斯特，被任命為新成立的巴爾的摩約翰斯·霍普金斯大學(xué)的首位數(shù)學(xué)教授。在那里，他建立了數(shù)學(xué)研究學(xué)派，并協(xié)助創(chuàng)辦了《美國數(shù)學(xué)雜志》

American Journal of Mathematics

，該期刊既刊登美國新銳數(shù)學(xué)家的文章，也收錄歐洲知名數(shù)學(xué)家的研究成果。

1878年6月13日，凱萊出席倫敦數(shù)學(xué)會會議時，詢問四色地圖著色問題是否已得到解決。他很快對這一問題產(chǎn)生了濃厚興趣，并應(yīng)好友弗朗西斯·高爾頓的邀請，為《皇家地理學(xué)會會刊》

Royal Geographical Society’s Proceedings

撰寫了一篇題為《論地圖著色》

On the colouring of maps

的短文。

在這篇短文中，凱萊承認(rèn)自己無法找到證明，并試圖解釋問題的難點(diǎn)所在。更重要的是，他闡明了如何將一般地圖的著色問題簡化為三次地圖（cubic maps）的情況——三次地圖指每個交點(diǎn)恰好連接三個區(qū)域的地圖。對于任何有超過三個區(qū)域交匯的地圖，只需在該交點(diǎn)處貼上一個“補(bǔ)丁”，即可轉(zhuǎn)化為三次地圖（見圖4）。如果這個三次地圖可以用四種顏色著色，那么將所有補(bǔ)丁縮小為一個點(diǎn)，就能得到原地圖的著色方案。這是一項重要進(jìn)展：此后，地圖著色研究者只需專注于三次地圖即可。

圖4 三次地圖的四色問題

（原始地圖→添加補(bǔ)丁→著色地圖→縮小補(bǔ)丁的示意圖）

3. 阿爾弗雷德·肯普（Alfred Kempe）

圖5 阿爾弗雷德·肯普（1849-1922）

出席1878年6月13日會議的還有阿爾弗雷德·布雷·肯普（Alfred Bray Kempe），他是一名律師，曾是凱萊在三一學(xué)院的數(shù)學(xué)學(xué)生?？掀請孕抛约耗軌蜃C明四色定理，經(jīng)過數(shù)月研究，他完成了一篇論文[9]。在時任主編西爾維斯特的邀請下，這篇論文被提交至《美國數(shù)學(xué)雜志》并正式發(fā)表，他還將論文預(yù)覽版寄給了科學(xué)期刊《自然》

Nature

肯普在論文中證明，每個三次地圖必定包含至少一個邊界邊數(shù)不超過五的區(qū)域——即二邊形（digon）、三角形（triangle）、四邊形（square）或五邊形（pentagon）。這一結(jié)論可通過歐拉多面體公式（Euler’s polyhedron formula）推導(dǎo)得出：對于任何具有R個區(qū)域、E條邊和N個區(qū)域交點(diǎn)的平面地圖，滿足

N - E + R = 2。

若用c?表示具有k條邊界邊的區(qū)域數(shù)量，則有3N = 2E（因為每條邊連接兩個交點(diǎn)），因此：

R = c? + c? + c? + c? + c? + c? + c? +? ,

2E = 3N = 2c? + 3c? + 4c? + 5c? + 6c? + 7c? + 8c? + ?

將這些表達(dá)式代入歐拉公式，可得到計數(shù)公式：

4c? + 3c? + 2c? + c? - c? - 2c? - ? = 12

因此，若不存在邊界邊數(shù)不超過五的區(qū)域，上式左邊將為負(fù)數(shù)，產(chǎn)生矛盾。

如果地圖中包含二邊形或三角形，通過數(shù)學(xué)歸納法可直接證明：先給地圖其余部分著色，必然會剩余一種顏色用于給二邊形或三角形著色。但如果地圖中包含四邊形S，它可能被四種顏色（例如按順序排列的紅r、藍(lán)b、綠g、黃y）的區(qū)域包圍。為解決這種情況，肯普提出了一種有效的顏色交換論證方法，即后來著名的肯普鏈法（method of Kempe chains）。

圖6 肯普鏈法示意圖

肯普觀察了與四邊形S相鄰的紅-綠顏色區(qū)域（見圖6）。如果這些區(qū)域沒有形成連通鏈，那么交換其中一部分紅-綠顏色，就能為S騰出一種顏色。但如果它們形成了紅-綠連通鏈，交換顏色并不會改善情況。不過在這種情況下，與S相鄰的藍(lán)-黃顏色區(qū)域會被紅-綠鏈分隔，因此可以交換其中一部分藍(lán)-黃顏色，同樣能為S騰出顏色。因此，無論哪種情況，四邊形S都能被著色，結(jié)論通過歸納法成立。

隨后，肯普轉(zhuǎn)向剩余情況——地圖中包含五邊形P。如果地圖其余部分已著色，且五邊形P被四種顏色包圍（其中一種顏色出現(xiàn)兩次），那么通過兩次顏色交換，就能消除該顏色的重復(fù)出現(xiàn)，從而為P騰出一種顏色，證明即可完成。

這一論證似乎涵蓋了所有可能情況，但正如我們后續(xù)將發(fā)現(xiàn)的，肯普的最后一步存在缺陷，他的證明也成為了數(shù)學(xué)史上最著名的錯誤證明之一。

更具價值的是，肯普還提出了另一個重要思想：對地圖區(qū)域的任何著色方案，都對應(yīng)著對區(qū)域首都的著色（見圖7）。若將每對相鄰區(qū)域的首都用線段連接，就得到了肯普所說的“連接圖”（linkage）。此時，四色問題轉(zhuǎn)化為：用四種顏色給這些首都著色，使得任何兩個通過線段連接的首都顏色不同。正如我們將看到的，這種將地圖區(qū)域著色轉(zhuǎn)化為平面圖（planar graph）頂點(diǎn)著色的對偶形式，后來成為四色問題的標(biāo)準(zhǔn)表述。

圖7 連接圖著色示意圖

（國家著色→描繪連接圖→頂點(diǎn)用顏色字母標(biāo)記的示意圖）

肯普提交論文時，西爾維斯特正在英國夏季旅行，論文由他在約翰斯·霍普金斯大學(xué)的同事、期刊聯(lián)合創(chuàng)始人兼副主編威廉·斯托里（William Story）處理。斯托里未能發(fā)現(xiàn)肯普證明中的主要錯誤，但指出了其中的一些小漏洞，并撰寫了一篇題為《對前文的注釋》

Note on the preceding paper

的短文，附在肯普的論文之后。斯托里對四色問題的興趣持續(xù)了多年，在肯普的錯誤被發(fā)現(xiàn)后，他與C. S. 皮爾士就該問題進(jìn)行了通信交流。

與此同時，阿爾弗雷德·肯普發(fā)表了多篇關(guān)于機(jī)械連接裝置幾何性質(zhì)的著名論文。憑借這些研究成果以及他所謂的四色問題解決方案，他于1881年當(dāng)選為倫敦皇家學(xué)會會士。后來，他擔(dān)任該學(xué)會的司庫，期間資助了一次重要的南極探險，探險隊發(fā)現(xiàn)的肯普冰川（Kempe glacier）和肯普山（Mount Kempe）便是以他的名字命名的。

4. 彼得·格思里·泰特（Peter Guthrie Tait）

肯普的“證明”被廣泛接受為四色問題的解決方案。但在蘇格蘭，數(shù)學(xué)物理學(xué)家彼得·格思里·泰特（Peter Guthrie Tait）于1880年在《愛丁堡皇家學(xué)會會刊》上發(fā)表短文，批評肯普的論證過于復(fù)雜，且未能揭示問題的本質(zhì)。作為回應(yīng)，泰特提出了幾個更簡短、更簡潔的證明，但均存在缺陷。

圖8 彼得·格思里·泰特（1831-1901）

同年晚些時候，泰特提出了一個更具建設(shè)性的想法：給三次地圖的區(qū)域著色（四種顏色），等價于給地圖的邊界邊著色（三種顏色），且每個交點(diǎn)處的三條邊顏色各不相同（見圖9）。他認(rèn)為這種替代表述比原始問題更容易證明。盡管這一觀點(diǎn)并不正確，但邊著色（edge-colorings）后來成為了一個重要的研究課題。

圖9 泰特的等價表述示意圖

由于肯普的證明被認(rèn)為是該問題的最終答案，其他數(shù)學(xué)家也開始對四色問題產(chǎn)生興趣。牛津大學(xué)數(shù)學(xué)講師查爾斯·L·道奇森（Charles L. Dodgson）——即著名小說《愛麗絲夢游仙境》的作者劉易斯·卡羅爾（Lewis Carroll）——將其設(shè)計成一款雙人游戲。布里斯托爾附近的私立學(xué)校克利夫頓學(xué)院的校長，或許是受到泰特簡短“證明”的啟發(fā)，將四色問題作為學(xué)校的挑戰(zhàn)題，并規(guī)定“解決方案不得超過1頁手稿、30行文字和1頁圖表”。他還將問題寄給《教育期刊》

Journal of Education

，邀請讀者嘗試解決。倫敦主教弗雷德里克·坦普爾（Frederick Temple）——曾是牛津大學(xué)數(shù)學(xué)講師，后來成為坎特伯雷大主教——在一次冗長乏味的會議中走神時，找到了一個“解決方案”。但他僅僅證明了平面上不存在五個兩兩相鄰的區(qū)域，而正如我們之前所指出的，這并不能證明四色定理。

5. 珀西·希伍德（Percy Heawood）

1890年，一篇題為《地圖著色定理》

Map-colour theorem

[10]的開創(chuàng)性論文發(fā)表，該論文將四色問題的解決推遲了86年。論文作者是珀西·約翰·希伍德（Percy John Heawood），他在牛津大學(xué)學(xué)習(xí)數(shù)學(xué)期間了解到四色問題。獲得牛津?qū)W位后，他前往達(dá)勒姆學(xué)院（后來的達(dá)勒姆大學(xué)）任教，并在那里度過了余生。希伍德是一位深受愛戴但略顯古怪的學(xué)者：他每年只在圣誕節(jié)那天校準(zhǔn)一次手表，若一天沒有參加至少一次委員會會議，就認(rèn)為這一天是“浪費(fèi)的”。

圖10 珀西·希伍德（1861-1955）

自牛津求學(xué)時期起，希伍德就對四色問題著迷。他驚訝地發(fā)現(xiàn)，肯普的證明存在一個根本性缺陷。

他在論文中指出，肯普在處理五邊形情況時，假設(shè)可以同時進(jìn)行兩次顏色交換，但希伍德通過一個具體例子證明了這是不可行的。在他的例子中（見圖11），未著色的五邊形位于中心，人們可以交換五邊形上方區(qū)域的紅-綠顏色，或交換下方區(qū)域的紅-黃顏色，但如果同時進(jìn)行這兩次交換，圖右側(cè)的綠色區(qū)域和黃色區(qū)域都會變成紅色，這違反了著色規(guī)則。

圖11 希伍德的反例示意圖

幸運(yùn)的是，希伍德通過改進(jìn)肯普的論證，證明了每個地圖都可以用五種顏色著色——這本身就是一項重要成果。

希伍德還討論了一個相關(guān)問題——帝國問題（empire problem）：每個國家都有一個附屬區(qū)域（衛(wèi)星區(qū)域），附屬區(qū)域必須與宗主國顏色相同。他證明了所有此類三次地圖都可以用12種顏色著色，并“歷經(jīng)艱辛”找到了一個需要全部12種顏色的具體例子（見圖12）。注意，每個由兩個區(qū)域組成的帝國都與其他所有帝國相鄰。

圖12 帝國問題示意圖

隨后，希伍德觀察到平面地圖與球面地圖的著色問題是等價的，并進(jìn)一步研究了其他可定向曲面上——如帶有g(shù)個手柄的球面S(g)——三次地圖的著色所需顏色數(shù)。例如，環(huán)面（torus）S(1)上的任何地圖都可以用7種顏色著色，希伍德還構(gòu)造了一個需要全部7種顏色的環(huán)面地圖。

但希伍德的研究也存在錯誤。對于可定向曲面S(g)上具有R個區(qū)域、E條邊和N個交點(diǎn)的三次地圖，歐拉公式為N - E + R = 2 - 2g?；谶@一公式，希伍德推導(dǎo)出該地圖的區(qū)域著色所需顏色數(shù)為?(7 + √(48g + 1))/2?，

但對于所有g(shù) > 1的情況，他未能證明存在確實需要該數(shù)量顏色的地圖——這一斷言被稱為希伍德猜想（Heawood conjecture）。直到1968年，這一猜想才被完整證明[參見2, 3]。

1898年，希伍德發(fā)表了第二篇關(guān)于四色問題的論文，將其重新表述為數(shù)值同余問題。他首先證明，泰特對三次地圖邊的著色，等價于給每個交點(diǎn)分配數(shù)字1或-1，使得每個區(qū)域周圍的數(shù)字之和是3的倍數(shù)（見圖13）。此外，若交點(diǎn)標(biāo)記為p?, p?, ... , p?，則每個區(qū)域都對應(yīng)一個同余式z? + z? + ... + z? ≡ 0 (mod 3)，其中每個z?為1或-1，且當(dāng)交點(diǎn)p?位于該區(qū)域的某條邊界邊上時，z?會出現(xiàn)在同余式中。

圖13 希伍德對三次地圖交點(diǎn)的標(biāo)記示意圖

在畢生尋求四色定理證明的過程中，希伍德持續(xù)探索這一同余關(guān)系，最終在90歲時發(fā)表了相關(guān)論文。

6. 保羅·韋尼克（Paul Wernicke）

希伍德指出肯普證明的缺陷后，肯普試圖修正自己的證明，但未能成功。一些數(shù)學(xué)家甚至開始懷疑四色定理的正確性，丹麥數(shù)學(xué)家尤利烏斯·彼得森（Julius Petersen）曾表示：

“我無法確定任何事情，但如果要下注，我會堅持認(rèn)為四色定理是不正確的。”

大約在同一時期，德國數(shù)學(xué)家赫爾曼·閔可夫斯基（Hermann Minkowki）在哥廷根大學(xué)講授拓?fù)鋵W(xué)（analysis situs）課程。他聲稱，四色定理之所以未能被證明，是因為只有三流數(shù)學(xué)家嘗試過這一任務(wù)，并向?qū)W生吹噓自己能找到證明。隨后的幾周里，他在課堂上試圖證明該定理，但最終未能成功，不得不承認(rèn)自己也失敗了。

20世紀(jì)的第一個新想法來自保羅·韋尼克（Paul Wernicke）。他于1866年出生在德國，獲得數(shù)學(xué)學(xué)位后，于1893年移民美國并成為美國公民。他在肯塔基州擔(dān)任現(xiàn)代語言教師，但主要興趣仍在數(shù)學(xué)領(lǐng)域，后來返回德國撰寫了一篇關(guān)于拓?fù)鋵W(xué)的博士論文，之后再次回到美國。

韋尼克長期關(guān)注四色問題。在德國期間，他為《數(shù)學(xué)年刊》

Mathematische Annalen

撰寫了一篇重要論文，證明了任何不包含二邊形、三角形或四邊形的三次地圖，不僅必然包含五邊形，還必然包含兩個相鄰的五邊形，或一個與六邊形相鄰的五邊形（見圖14）。他希望后兩種構(gòu)型能比單純的五邊形更容易研究。

圖14 韋尼克的不可避免集示意圖

（二邊形、三角形、四邊形、兩個相鄰的五邊形、五邊形與六邊形相鄰的示意圖）

圖15 環(huán)大小為14的構(gòu)型示意圖

由此，地圖中“不可避免集”（unavoidable set）的核心概念應(yīng)運(yùn)而生。環(huán)大小為k的構(gòu)型，指的是由k個區(qū)域組成的環(huán)所包圍的一個或多個區(qū)域（見圖15）；若每個三次地圖都必然包含該集合中的至少一個構(gòu)型，則該集合稱為不可避免集。這一概念由肯普提出，經(jīng)韋尼克發(fā)展，成為后來解決四色問題的關(guān)鍵。

7. 奧斯瓦爾德·維布倫（Oswald Veblen）

1912年是四色問題研究的重要一年，兩篇具有里程碑意義的論文在美國《數(shù)學(xué)年刊》

Annals of Mathematics

上發(fā)表，作者分別是奧斯瓦爾德·維布倫（Oswald Veblen）和喬治·伯克霍夫（George Birkhoff）。加之伯克霍夫在次年發(fā)表的一篇開創(chuàng)性論文，四色問題的研究進(jìn)入了新的發(fā)展階段。

圖16 奧斯瓦爾德·維布倫（1880-1960）

奧斯瓦爾德·維布倫出生于愛荷華州，14歲進(jìn)入愛荷華大學(xué)，后轉(zhuǎn)入哈佛大學(xué)，最終在芝加哥大學(xué)獲得幾何學(xué)博士學(xué)位——幾何學(xué)也是他最具代表性的研究領(lǐng)域。1905年至1932年，他在普林斯頓大學(xué)任教，之后成為新成立的高等研究院（IAS）的首位數(shù)學(xué)教授。

在題為《模方程在拓?fù)鋵W(xué)中的應(yīng)用》

An application of modular equations in analytic situs

的論文中，維布倫運(yùn)用幾何學(xué)和代數(shù)學(xué)思想來研究四色問題。他首先引入兩個矩陣來描述具有給定頂點(diǎn)（交點(diǎn)）、邊界邊和區(qū)域標(biāo)記的地圖：點(diǎn)-邊關(guān)聯(lián)矩陣（vertex–edge incidence matrix）A，其中第(i,j)項為1當(dāng)且僅當(dāng)頂點(diǎn)i位于邊j上，否則為0；邊-區(qū)域關(guān)聯(lián)矩陣（edge–region incidence matrix）B，其中第(i,j)項為1當(dāng)且僅當(dāng)邊i與區(qū)域j相鄰，否則為0。

每個矩陣都對應(yīng)兩組線性方程組；例如，對于矩陣B，方程組中的變量代表地圖的區(qū)域，每條邊對應(yīng)一個形式為y? + yb = 0的方程，其中y?和yb代表沿該邊相鄰的兩個區(qū)域。維布倫將四元有限域（finite field）中的元素作為四種顏色，證明了四色問題的解等價于找到一組滿足所有上述方程的變量值{y?}。

維布倫進(jìn)一步發(fā)展了這些思想，將四色問題表述為有限射影空間（finite projective space）的子空間問題。他還證明了由矩陣A導(dǎo)出的一組方程組，與我們之前提到的希伍德同余式是等價的。

8. 喬治·伯克霍夫（George Birkhoff）

1912年初，維布倫在普林斯頓大學(xué)的好友兼同代人喬治·戴維·伯克霍夫（George David Birkhoff），成為20世紀(jì)早期最具影響力的全能數(shù)學(xué)家之一。他出生于密歇根州，早年就展現(xiàn)出非凡的數(shù)學(xué)天賦。1902年，他進(jìn)入芝加哥大學(xué)，與維布倫首次相遇。在芝加哥大學(xué)學(xué)習(xí)一年后，他轉(zhuǎn)入哈佛大學(xué)攻讀學(xué)士和碩士學(xué)位，隨后返回芝加哥大學(xué)，撰寫了關(guān)于微分方程的博士論文。在威斯康星大學(xué)任教兩年后，他轉(zhuǎn)入普林斯頓大學(xué)并晉升為教授，1912年回到哈佛大學(xué)，此后一直在該校任教直至去世。

圖17 喬治·伯克霍夫（1884-1944）

盡管伯克霍夫最著名的研究領(lǐng)域是動力系統(tǒng)、微分方程和遍歷理論等，但他畢生都對四色問題充滿興趣。為了尋求證明，他常常讓妻子繪制復(fù)雜的地圖供自己著色。

伯克霍夫研究地圖著色的第一個方法是定量分析：計算用k種顏色給給定地圖著色的方式數(shù)P(k)。例如，對于四個兩兩相鄰的區(qū)域組成的地圖，有：

P(k) = k(k - 1)(k - 2)(k - 3)

= k? - 6k3 + 11k2 - 6k

他證明了P(k)始終是k的多項式（現(xiàn)稱為地圖的(染、著、涂)色多項式，chromatic polynomial），并指出：若地圖有n個區(qū)域和m條邊，則P(k)的首項為k? - mk??1，同時給出了其他所有系數(shù)的計算公式。他希望通過對這些多項式的一般研究，證明所有地圖都滿足P(4) > 0（即存在四種顏色的著色方案）。

伯克霍夫?qū)ι囗検降呐d趣貫穿一生，分別于1930年和1934年發(fā)表了相關(guān)論文。1930年的論文由哈斯勒·惠特尼（Hassler Whitney）整理——惠特尼后來成為拓?fù)鋵W(xué)先驅(qū)，他關(guān)于四色問題的想法給伯克霍夫留下了深刻印象，并在伯克霍夫的指導(dǎo)下完成了題為《圖的著色》

The Coloring of Graphs

的博士論文；惠特尼還發(fā)表了一篇關(guān)于色多項式的著名論文，提出了一種更簡潔的系數(shù)計算方法，并證明了這些系數(shù)的符號始終交替變化。伯克霍夫去世后，與他的前研究生丹尼爾·C·劉易斯（Daniel C. Lewis）合作撰寫的一篇關(guān)于色多項式的長篇影響論文正式發(fā)表。

1913年，伯克霍夫在一篇開創(chuàng)性論文[11]中，為四色定理的最終解決做出了重要貢獻(xiàn)：他將“可約構(gòu)型”（reducible configuration）定義為：若包圍該構(gòu)型的環(huán)區(qū)域的所有著色方案，都能擴(kuò)展到構(gòu)型內(nèi)部的區(qū)域，則該構(gòu)型為可約構(gòu)型。由此可知，可約構(gòu)型不可能出現(xiàn)在四色定理的最小反例中。

伯克霍夫系統(tǒng)地證明了：所有環(huán)大小為3或4的構(gòu)型都是可約的；對于環(huán)大小為5的構(gòu)型，除了單個五邊形外，其余都是可約的。

他還證明了由四個五邊形組成、被環(huán)大小為6的區(qū)域包圍的伯克霍夫菱形（Birkhoff diamond）是可約的（見圖18）。該構(gòu)型的環(huán)區(qū)域共有31種本質(zhì)不同的著色方案：其中16種可直接擴(kuò)展到內(nèi)部的五邊形，其余15種需通過一次或多次肯普顏色交換才能擴(kuò)展。

圖18 伯克霍夫菱形示意圖

在隨后的幾十年里，更多的可約構(gòu)型被發(fā)現(xiàn)，數(shù)量最終達(dá)到數(shù)千種。

9. 菲利普·弗蘭克林（Philip Franklin）

1920年代至1930年代，四色問題的研究穩(wěn)步推進(jìn)。1921年，比利時數(shù)學(xué)家阿爾弗雷德·埃雷拉（Alfred Errera）為布魯塞爾大學(xué)撰寫了關(guān)于地圖著色的博士論文，并在此后發(fā)表了多篇相關(guān)論文，其中特別證明了：四色定理的每個最小反例都必須包含至少13個五邊形，且不能僅由五邊形和六邊形組成。

與此同時，美國數(shù)學(xué)家菲利普·弗蘭克林（Philip Franklin）開始涉足這一領(lǐng)域。他畢業(yè)于紐約城市學(xué)院，后轉(zhuǎn)入普林斯頓大學(xué)，在奧斯瓦爾德·維布倫的指導(dǎo)下完成了題為《四色定理》

The Four Color Theorem

的博士論文。隨后，他發(fā)表了一篇重要論文[12]，擴(kuò)展了關(guān)于不可避免集和可約構(gòu)型的現(xiàn)有知識。1924年，他加入麻省理工學(xué)院，此后一直在該校任教，研究領(lǐng)域廣泛，并撰寫了多部廣受好評的學(xué)生教材。

弗蘭克林在論文中利用肯普的計數(shù)公式，發(fā)現(xiàn)了更多可約構(gòu)型，例如與三個五邊形相鄰的五邊形、與四個五邊形和兩個六邊形相鄰的六邊形等。他還證明了：任何不包含二邊形、三角形或四邊形的地圖，都必然包含以下三種構(gòu)型之一：與兩個其他五邊形相鄰的五邊形、與兩個五邊形和一個六邊形相鄰的五邊形、與一個五邊形和兩個六邊形相鄰的五邊形——這一結(jié)論給出了新的不可避免集（見圖19）。此后，直到1940年，以勒貝格積分聞名的亨利·勒貝格（Henri Lebesgue）在其最后一篇論文中提出了多個新的不可避免集，這一領(lǐng)域才再添新成果。

圖19 弗蘭克林的不可避免集示意圖

（二邊形、三角形、四邊形、三個相鄰的五邊形、

兩個五邊形與一個六邊形相鄰、一個五邊形與兩個六邊形相鄰的示意圖）

弗蘭克林還推導(dǎo)出：所有區(qū)域數(shù)不超過25的地圖都可以用四種顏色著色。西弗吉尼亞大學(xué)的克拉倫斯·雷諾茲（Clarence Reynolds）進(jìn)一步將這一數(shù)字提高到27，而C. E. 溫（C. E. Winn）于1940年將其提升至35。

10. 海因里?！ず谑℉einrich Heesch）

第二次世界大戰(zhàn)后，四色定理的證明嘗試迎來了新的轉(zhuǎn)折，德國數(shù)學(xué)家海因里?！ず谑℉einrich Heesch）的出現(xiàn)推動了研究方向的轉(zhuǎn)變。他出生于基爾，在慕尼黑同時獲得數(shù)學(xué)和音樂學(xué)位，后在蘇黎世大學(xué)完成了關(guān)于幾何公理的博士論文。隨后，他轉(zhuǎn)入哥廷根大學(xué)，擔(dān)任赫爾曼·外爾（Hermann Weyl）的助手，從事晶體研究。期間，他因解決了平面鑲嵌圖案中的“正鑲嵌問題”（regular parquet problem）而聲名鵲起——這一問題是大衛(wèi)·希爾伯特（David Hilbert）1900年在巴黎國際數(shù)學(xué)家大會上發(fā)表著名演講時提出的“第18問題”的一部分。

但自1933年起，納粹對德國大學(xué)教職人員的清洗使得學(xué)術(shù)環(huán)境日益惡劣，黑施辭去了哥廷根大學(xué)的職位，返回基爾與父母同住。在隨后的12年里，他以教書為生，同時繼續(xù)研究鑲嵌圖案；其中一種圖案后來被應(yīng)用于哥廷根大學(xué)圖書館的天花板設(shè)計。

黑施于20世紀(jì)30年代中期首次了解到四色問題，并對其產(chǎn)生了畢生的興趣。他很快意識到，解決這一問題的關(guān)鍵在于找到一個“不可避免的可約構(gòu)型集”——“不可避免”意味著每個地圖都必須包含該集合中的至少一個構(gòu)型；“可約”意味著無論包含哪個構(gòu)型，地圖其余部分的所有著色方案都能擴(kuò)展到該構(gòu)型。換句話說，由于不可避免集中的可約構(gòu)型不可能出現(xiàn)在四色定理的最小反例中，因此這樣的反例不存在，四色定理成立。

1948年左右，黑施在基爾向大量聽眾發(fā)表了關(guān)于四色問題的演講。他提出，需要找到一個有限的不可避免可約構(gòu)型集，且該集合可能非常大——可能包含多達(dá)10000個構(gòu)型。為了便于分類，他將構(gòu)型定義為D-可約（D-reducible）：若包圍構(gòu)型的環(huán)區(qū)域的所有著色方案，都能通過直接著色或顏色交換擴(kuò)展到構(gòu)型內(nèi)部，則該構(gòu)型為D-可約。正如我們之前所見，二邊形、三角形、四邊形和伯克霍夫菱形都是D-可約的。他還將通過某種修改后可變?yōu)榭杉s構(gòu)型的構(gòu)型稱為C-可約（C-reducible）。

與此同時，黑施構(gòu)造了大量可約構(gòu)型，多年來培養(yǎng)出了一眼就能判斷構(gòu)型是否可約的能力——準(zhǔn)確率最終超過80%。為此，他指出了三種會阻礙構(gòu)型可約性的特征：“四腿區(qū)域”（4-legger region）——與環(huán)區(qū)域中四個連續(xù)區(qū)域相鄰；“三腿鉸接區(qū)域”（3-legger articulation region）——與環(huán)區(qū)域中三個非全部相鄰的區(qū)域相鄰；“懸掛5-5對”（hanging 5-5 pair）——兩個相鄰的五邊形，且均與環(huán)內(nèi)部的同一個區(qū)域相鄰（見圖20）。

圖20 阻礙可約性的三種特征示意圖

（四腿區(qū)域、三腿鉸接區(qū)域、懸掛5-5對的示意圖）

如前所述，當(dāng)時已知的不可避免集數(shù)量很少，但黑施發(fā)現(xiàn)了一種證明給定構(gòu)型集為不可避免集的有效方法——放電法（method of discharging）。該方法有多種形式，為了說明其基本思想，我們可以證明韋尼克的構(gòu)型集（見圖14）是不可避免集：

假設(shè)存在一個不包含二邊形、三角形、四邊形、兩個相鄰的五邊形以及五邊形與六邊形相鄰構(gòu)型的地圖——那么每個五邊形只能與邊數(shù)不少于七的區(qū)域相鄰。給每個k邊形區(qū)域分配一個“電荷”：6-k，則五邊形的電荷為1（單位電荷），六邊形的電荷為0，邊數(shù)超過六的多邊形電荷為負(fù)。根據(jù)肯普的計數(shù)公式，整個地圖的總電荷為12（正數(shù)）。若通過“放電”過程，將每個五邊形的單位電荷平均分配給其五個相鄰區(qū)域，則地圖的總電荷仍為正數(shù)，但此時每個五邊形的電荷變?yōu)?，六邊形的電荷仍為0，而其他區(qū)域獲得的電荷不足以使其變?yōu)檎龜?shù)——這導(dǎo)致總電荷非正，產(chǎn)生矛盾。因此，假設(shè)不成立，韋尼克的構(gòu)型集是不可避免集。

此時，圖論學(xué)科正在發(fā)展，大多數(shù)地圖著色研究者開始采用四色問題的“對偶形式”——即肯普的連接圖形式：不再給地圖區(qū)域著色（相鄰區(qū)域顏色不同），而是給平面圖的頂點(diǎn)著色，使得任何兩個相鄰頂點(diǎn)顏色不同。為此，黑施引入了對應(yīng)于五邊形、六邊形等區(qū)域的頂點(diǎn)符號（見圖21），這些符號后來被廣泛采用。

圖21 黑施的地圖區(qū)域符號示意圖

（五邊形、六邊形、七邊形、八邊形的符號及組合示意圖）

11. 沃爾夫?qū)す希╓olfgang Haken）

沃爾夫?qū)す希╓olfgang Haken）于1928年出生在柏林，早年就對數(shù)學(xué)表現(xiàn)出濃厚興趣。15歲時，他被征召加入二戰(zhàn)防空部隊，同時繼續(xù)完成學(xué)業(yè)，并于1946年初畢業(yè)。當(dāng)時，大多數(shù)德國大學(xué)不招收23歲以下的學(xué)生，但基爾大學(xué)是個例外，17歲的哈肯成為該校最年輕的學(xué)生。他在學(xué)年中期被錄取，攻讀數(shù)學(xué)、物理和哲學(xué)專業(yè)，直接進(jìn)入第二學(xué)期的課程學(xué)習(xí)，沒有任何前期基礎(chǔ)，但他最終成功跟上了進(jìn)度，并在后來將這一時期描述為“非常、非常令人興奮——對我來說，那是一段美好的時光”。

當(dāng)時基爾大學(xué)只有一位活躍的數(shù)學(xué)教授——卡爾-海因里?！の核梗↘arl-Heinrich Weise）。魏斯是一位優(yōu)秀的教師，1947年在拓?fù)鋵W(xué)課程中，他提到了三個未解決的問題：結(jié)問題（knot problem）、龐加萊猜想（Poincaré conjecture）和四色問題。這三個問題后來都成為哈肯畢生研究的重要部分：他解決了結(jié)問題，為龐加萊猜想的研究做出了重大貢獻(xiàn)，并最終與肯尼斯·阿佩爾共同解決了四色問題。

在基爾大學(xué)，哈肯結(jié)識了海因里?！ず谑?，并參加了他關(guān)于四色問題的演講。當(dāng)時哈肯對此理解不深，但后來回憶起，黑施提到需要系統(tǒng)研究約10000個特殊情況才能證明四色定理。這次演講在哈肯心中埋下了種子，并在數(shù)十年后開花結(jié)果。

1948年獲得學(xué)位后，哈肯在魏斯的指導(dǎo)下開始研究生階段的學(xué)習(xí)，于1953年完成了關(guān)于高維拓?fù)鋵W(xué)的博士論文。隨后，他移居慕尼黑，在西門子公司的研發(fā)部門從事微波技術(shù)工作。

在慕尼黑期間，哈肯始終保持著對數(shù)學(xué)的興趣，尤其對“結(jié)問題”——判斷給定的三維閉合曲線（如纏繞的繩子）是否打結(jié)——著迷。他利用業(yè)余時間研究這一問題，最終成功找到完整解決方案，并在1954年阿姆斯特丹國際數(shù)學(xué)家大會上宣布了這一成果。他面臨的困難是，在全職工作的同時，難以抽出時間撰寫完整的證明論文，但最終他還是完成了這項工作，其長篇證明發(fā)表在《數(shù)學(xué)學(xué)報》

Acta Mathematica

上。

伊利諾伊大學(xué)厄巴納-尚佩恩分校的邏輯學(xué)家比爾·布恩（Bill Boone）閱讀了哈肯的證明后，深受觸動，邀請他擔(dān)任該校的客座教授。在那里，哈肯就其打結(jié)問題的解決方案發(fā)表了演講。隨后，他在普林斯頓高等研究院工作了兩年，之后返回伊利諾伊大學(xué)，擔(dān)任終身教授。

哈肯隨后將注意力轉(zhuǎn)向證明龐加萊猜想。他處理難題的方法是：將問題視為一棵有許多枝葉的樹，逐一剪除枝葉，直至整棵樹被摧毀。對于龐加萊猜想，他找到了200個需要“剪除”的“枝葉”，并聲稱已剪除了198個，但在與最后兩個“枝葉”抗?fàn)幜耸旰?，他最終承認(rèn)失敗。

1967年，奧伊斯坦·奧爾（Oystein Ore）出版了關(guān)于四色問題的第一部專著[6]，同年，哈肯將注意力重新投向了這個二十年來未曾關(guān)注的問題。他首先聯(lián)系黑施，詢問他是否已解決四色問題，或是仍在研究那10000個特殊情況。此時，黑施已構(gòu)造出數(shù)千個可約構(gòu)型，但未能將它們整合為一個不可避免集。

哈肯邀請黑施到伊利諾伊大學(xué)發(fā)表關(guān)于四色問題的演講，并詢問他日益普及的計算機(jī)是否能幫助驗證如此多的構(gòu)型。當(dāng)時黑施在漢諾威自由大學(xué)工作，已聘請前研究生卡爾·迪爾（Karl Dürre）在該校的計算機(jī)上測試構(gòu)型的D-可約性——對于任何給定構(gòu)型，通過檢查包圍環(huán)區(qū)域的所有著色方案是否能直接或通過顏色交換擴(kuò)展到內(nèi)部區(qū)域，即可完成驗證。

如前所述，對于環(huán)大小為6的伯克霍夫菱形，需要檢查31種不同的環(huán)區(qū)域著色方案。但隨著構(gòu)型復(fù)雜度的增加，著色方案的數(shù)量會急劇增長——環(huán)大小每增加1，著色方案數(shù)量就會變?yōu)樵瓉淼?倍；對于環(huán)大小為14的構(gòu)型，需要考慮的著色方案多達(dá)199271種。由于需要驗證的構(gòu)型數(shù)量眾多，當(dāng)時的計算機(jī)需要數(shù)千小時才能完成，這在當(dāng)時看來是難以實現(xiàn)的。

伊利諾伊大學(xué)沒有可用的計算機(jī)，但該校計算機(jī)系設(shè)法安排黑施和迪爾使用長島布魯克海文國家實驗室的大型Cray計算機(jī)。實驗室主任島本（Yoshio Shimamoto）本人也對四色問題著迷，邀請他們在布魯克海文實驗室長期工作。當(dāng)時已得知，任何解決方案都必然涉及環(huán)大小不小于12的構(gòu)型，而Cray計算機(jī)使他們能夠驗證許多環(huán)大小為13的構(gòu)型的D-可約性，并開始著手處理環(huán)大小為14的構(gòu)型。

在研究過程中，島本發(fā)現(xiàn)了一個環(huán)大小為14的單一構(gòu)型——所謂的“島本馬蹄形”（Shimamoto horseshoe），若該構(gòu)型被證明是D-可約的，將直接證明四色定理。這一消息迅速傳遍全球，但經(jīng)過26小時的連續(xù)計算，計算機(jī)最終證實該馬蹄形構(gòu)型并非D-可約，令所有人失望不已。

12. 肯尼斯·阿佩爾（Kenneth Appel）

1970年左右，黑施開發(fā)了一些新的放電過程，他認(rèn)為這些過程可將四色問題簡化為8900個難以處理的構(gòu)型（環(huán)大小最大為18），只需逐一驗證這些構(gòu)型即可。但此時，哈肯對需要處理如此多復(fù)雜情況的前景感到失望，在伊利諾伊大學(xué)的一次演講中，他宣布：

“計算機(jī)專家告訴我，這樣的研究方式是不可行的?，F(xiàn)在，我決定放棄。我認(rèn)為，這是無需計算機(jī)就能達(dá)到的極限?！?/p>

出席這次演講的有肯尼斯·阿佩爾（Kenneth Appel），他在密歇根大學(xué)完成了關(guān)于數(shù)理邏輯與代數(shù)學(xué)關(guān)聯(lián)的博士論文。阿佩爾是一位技藝高超的計算機(jī)程序員，在密歇根大學(xué)期間學(xué)會了編程技能，職業(yè)生涯中曾任職于道格拉斯飛機(jī)公司，并在普林斯頓國防分析研究所從事研究，1961年轉(zhuǎn)入伊利諾伊大學(xué)。

演講時，阿佩爾正擔(dān)任哈肯一名研究生的博士論文評審，該論文涉及四色問題的一個方面。在哈肯宣布放棄后，阿佩爾向他提出了一個建議：

“我認(rèn)為沒有什么是計算機(jī)做不到的——有些事情只是需要更長時間而已。我們?yōu)槭裁床辉囈辉嚹兀俊?/p>

圖22 肯尼斯·阿佩爾（1932—2013）與沃爾夫?qū)す希?928—2022）

在此之前，大多數(shù)地圖著色研究者都是先尋找大量可約構(gòu)型，再試圖將它們整合為不可避免集，但均以失敗告終。而哈肯的方法則不同：他先構(gòu)建由“可能可約”的構(gòu)型組成的不可避免集，再驗證這些構(gòu)型的可約性；對于無法輕易證明為可約的構(gòu)型，則用其他構(gòu)型替代。他希望通過這種迭代過程，更快地找到不可避免的可約構(gòu)型集。

當(dāng)阿佩爾和哈肯開始實踐這一想法時，計算機(jī)輸出的構(gòu)型列表中存在大量重復(fù)項，但阿佩爾很快引入了一些簡單的修改，減少了重復(fù)。這迅速成為一個持續(xù)的實驗過程：阿佩爾和哈肯定期調(diào)整放電算法，改進(jìn)計算機(jī)程序，以優(yōu)化構(gòu)型列表。

為簡化問題，他們將研究范圍限制在不包含黑施提出的三種可約性障礙的構(gòu)型上，因為這些構(gòu)型不太可能出現(xiàn)在最終的不可避免集中。起初，他們專注于僅排除前兩種障礙（四腿區(qū)域和三腿鉸接區(qū)域）的“地理良好”構(gòu)型，并認(rèn)為在幾個月內(nèi)構(gòu)建出此類構(gòu)型的不可避免集是可行的?；谶@一想法，他們在1974年花費(fèi)了數(shù)月時間，通過理論論證證實了此類不可避免集的存在，并提出了可實現(xiàn)的構(gòu)造方法。

漸漸地，阿佩爾和哈肯意識到，盡管D-可約構(gòu)型通常易于處理（若規(guī)模不太大），但C-可約構(gòu)型需要進(jìn)行修改，且修改方式尚不明確，因此需要外界幫助。阿佩爾聯(lián)系了該校計算機(jī)科學(xué)系，發(fā)現(xiàn)研究生約翰·科赫（John Koch）愿意提供幫助。阿佩爾委托他尋找修改環(huán)大小為11的C-可約構(gòu)型的簡單方法，科赫成功完成了這一任務(wù)，隨后阿佩爾將科赫的方法擴(kuò)展到更大環(huán)的構(gòu)型。

1975年，阿佩爾和哈肯引入了黑施提出的第三種可約性障礙（懸掛5-5對），并欣慰地發(fā)現(xiàn)，這一修改僅使不可避免集的規(guī)模增加了一倍。在接下來的幾個月里，他們持續(xù)改進(jìn)方法，最終形成了一種“人機(jī)對話”模式——計算機(jī)似乎能自主發(fā)現(xiàn)改進(jìn)方案，優(yōu)化了預(yù)設(shè)程序。

此時，他們已確信能夠找到一個無障礙、且構(gòu)型大概率可約的不可避免集，且問題構(gòu)型的數(shù)量會很少。令他們感到寬慰的是，研究表明無需處理環(huán)大小超過14的構(gòu)型。1976年上半年，他們繼續(xù)改進(jìn)放電方法，并以這些復(fù)雜構(gòu)型為指導(dǎo)，完善研究方案。

1976年3月，伊利諾伊大學(xué)購置了一臺功能強(qiáng)大的新計算機(jī)，春假期間該計算機(jī)基本閑置，阿佩爾得以利用它高效完成構(gòu)型可約性的大規(guī)模驗證工作。這一舉措為他們節(jié)省了數(shù)月的繁瑣勞動，令他們驚喜的是，驗證工作于6月完成。為慶祝這一成果，阿佩爾在數(shù)學(xué)系的黑板上寫下：

“經(jīng)仔細(xì)驗證，四種顏色足夠。”（Modulo careful checking it appears that four colors suffice.）

在家人的幫助下，最終驗證工作在幾周內(nèi)完成，形成了包含1936個可約構(gòu)型的不可避免集。1976年7月22日，他們正式公布了這一結(jié)果，告知同事，并向該領(lǐng)域的其他研究者發(fā)送了預(yù)印本。

圖23 證明公布后數(shù)學(xué)系的郵戳示意圖

（印有“四種顏色足夠”（FOUR COLORS SUFFICE）字樣的郵戳）

13. 后續(xù)發(fā)展

阿佩爾、哈肯和科赫的研究恰逢其時——當(dāng)時一些競爭對手也即將完成解決方案。著名組合數(shù)學(xué)家比爾·塔特（Bill Tutte）認(rèn)可了他們的成果，他們的成功被全球報紙報道。阿佩爾和哈肯為美國數(shù)學(xué)會撰寫了一篇簡短的“研究公告”[13]，概述了證明的核心思想。

1977年12月，阿佩爾和哈肯在《伊利諾伊數(shù)學(xué)期刊》

Illinois Journal of Mathematics

上發(fā)表了關(guān)于證明中放電過程的長篇論文[14]，并與約翰·科赫合作發(fā)表了關(guān)于可約性的后續(xù)論文[15]；這些論文附帶了一張包含450頁詳細(xì)解釋和圖表的縮微膠片。此時，作者們已發(fā)現(xiàn)列表中存在許多重復(fù)構(gòu)型和包含關(guān)系，出版的構(gòu)型列表被縮減至1482個。隨后發(fā)現(xiàn)的一些錯誤也得到了修正，但阿佩爾和哈肯知道，由于證明本身具有很強(qiáng)的自我修正能力，少數(shù)有問題的構(gòu)型總能被輕易替換。

這一長期懸而未決的問題，最終通過計算機(jī)輔助證明得以解決——這一成果令一些人歡欣鼓舞，也讓許多人感到不安和失望，還有一部分人則完全拒絕接受這種無法手動驗證的數(shù)學(xué)論證。

圖24 阿佩爾和哈肯的部分可約構(gòu)型示意圖

1986年，阿佩爾和哈肯發(fā)表了一篇輕松的文章《四色證明已足夠》

The four color proof suffices

[16]，回應(yīng)了諸多批評；三年后，他們出版了一部大部頭著作[17]，修正了所有已發(fā)現(xiàn)的錯誤，并收錄了縮微膠片的打印版。

1994年，尼爾·羅伯遜（Neil Robertson）、保羅·西摩（Paul Seymour）、丹尼爾·桑德斯（Daniel Sanders）和羅賓·托馬斯（Robin Thomas）合作，重新優(yōu)化了阿佩爾-哈肯的證明方法，使其更簡潔、系統(tǒng)，并得到了一個僅包含633個可約構(gòu)型的更簡單不可避免集[18]——羅伯遜和西摩多年來一直利用暑期時間解決圖論中的開放問題。十年后，法國計算機(jī)科學(xué)家喬治·貢蒂埃（Georges Gonthier）[19]對他們的方法進(jìn)行了完整的機(jī)器驗證，核實了60000行形式語言證明，最終宣布該證明完全正確。至此，四色定理終于被認(rèn)為得到了徹底證明。

參考文獻(xiàn)[1-8]包含了關(guān)于四色定理歷史和證明的更多信息，以及本文引用論文的詳細(xì)參考文獻(xiàn)。參考文獻(xiàn)[9-12, 18-19]是本文提及的著名論文，[13-17]是阿佩爾和哈肯的相關(guān)著作。

原文參考文獻(xiàn)

[1] Robin Wilson, Four colors suffice: How the map problem was solved, Princeton Science Library, Princeton University Press, Princeton, NJ, 2014. Revised color edition of the 2002 original, with a new foreword by Ian Stewart. MR3235839.

[2] Robin Wilson, John J. Watkins, and David J. Parks, Graph theory in America—the first hundred years, Princeton University Press, Princeton, NJ, 2023, DOI 10.2307/j.ctv2sbm8p2. MR4574842.

[3] Lowell W. Beineke, Bjarne Toft, and Robin J. Wilson, Milestones in graph theory—a century of progress, AMS/MAA Spectrum, vol. 108, MAA Press, Providence, RI, 2025. MR4922623.

[4] Donald MacKenzie, Slaying the Kraken: the sociohistory of a mathematical proof, Soc. Stud. Sci. 29 (1999), no. 1, 7–60, DOI 10.1177/030631299029001002. MR1692830.

[5] Rudolf Fritsch and Gerda Fritsch, The four-color theorem: History, topological foundations, and idea of proof, Springer-Verlag, New York, 1998. Translated from the 1994 German original by Julie Peschke, DOI 10.1007/978-1-4612-1720-6. MR1633950.

[6] Oystein Ore, The four-color problem, Pure and Applied Mathematics, vol. 27, Academic Press, New York-London, 1967. MR216979.

[7] Thomas L. Saaty and Paul C. Kainen, The four-color problem: Assaults and conquest, McGraw-Hill International Book Co., New York-Bogotá-Auckland, 1977. MR480047.

[8] Hans-Günther Bigalke, Heinrich Heesch (German), Vita Mathematica, vol. 3, Birkh?user Verlag, Basel, 1988. Kristallgeometrie. Parkettierungen. Vierfarbenforschung. [Geometry of crystals. Tilings. Four color problem], DOI 10.1007/978-3-0348-7246-1. MR946224.

[9] A. B. Kempe, On the geographical problem of the four colours, Amer. J. Math. 2 (1879), no. 3, 193–200, DOI 10.2307/2369235. MR1505218.

[10] P. J. Heawood, Map-colour theorem, Quarterly J. Pure and Applied Math. 24 (1890), 332–338.

[11] George D. Birkhoff, The reducibility of maps, Amer. J. Math. 35 (1913), no. 2, 115–128, DOI 10.2307/2370276. MR1506176.

[12] Philip Franklin, The four color problem, Amer. J. Math. 44 (1922), no. 3, 225–236, DOI 10.2307/2370527. MR1506473.

[13] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976), no. 5, 711–712, DOI 10.1090/S0002-9904-1976-14122-5. MR424602.

[14] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR543792.

[15] K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR543793.

[16] K. Appel and W. Haken, The four color proof suffices, Math. Intelligencer 8 (1986), no. 1, 10–20, 58, DOI 10.1007/BF03023914. MR823216.

[17] Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, Contemporary Mathematics, vol. 98, American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch, DOI 10.1090/conm/098. MR1025335.

[18] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44, DOI 10.1006/jctb.1997.1750. MR1441258

[19] Georges Gonthier, Formal proof—the four-color theorem, Notices Amer. Math. Soc. 55 (2008), no. 11, 1382–1393. MR2463991

參考資料

https://www.ams.org/journals/notices/202603/noti3305/noti3305.html

小樂數(shù)學(xué)科普近期文章

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點(diǎn)贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點(diǎn)擊zzllrr小樂

公眾號主頁

右上角

置頂加星★

數(shù)學(xué)科普不迷路！