四色定理誕生歷程：1852—1976——譯自AMS Notices美國數學會通告

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

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

作者：羅賓·威爾遜（Robin Wilson）《美國數學會通告》

AMS Notices

2026-3

譯者：zzllrr小樂（數學科普公眾號）2026-2-25

作者簡介

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

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

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

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

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

Budget of Paradoxes

收錄了他在當時的文學與科學期刊《雅典娜神廟》

The Athenaeum

上發表的大量文章，于1872年出版。1865年，他當選為倫敦數學會首任主席。

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

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

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

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

Proceedings of Edinburgh’s Royal Society

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

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

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

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

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

Tinting Maps

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

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

2. 阿瑟·凱萊（Arthur Cayley）

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

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

阿瑟·凱萊出生于倫敦，但早年隨經商的父親在俄羅斯生活。回到英國后，他在倫敦接受教育，17歲時進入劍橋大學三一學院。1840年以優異成績畢業后，他被任命為學院研究員，但由于需要接受英國國教的圣職，他于1844年離開劍橋，在倫敦的律師學院擔任了19年的成功律師。在此期間，他撰寫了超過300篇數學論文，并結識了好友兼合作者詹姆斯·約瑟夫·西爾維斯特（James Joseph Sylvester），兩人共同開創了代數學的新領域——不變量理論（invariant theory）。1863年，他回到劍橋，擔任首任薩德勒（Sadleirian）純粹數學教授，并在此職位上度過余生。

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

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

American Journal of Mathematics

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

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

Royal Geographical Society’s Proceedings

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

On the colouring of maps

的短文。

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

圖4 三次地圖的四色問題

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

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

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

出席1878年6月13日會議的還有阿爾弗雷德·布雷·肯普（Alfred Bray Kempe），他是一名律師，曾是凱萊在三一學院的數學學生。肯普堅信自己能夠證明四色定理，經過數月研究，他完成了一篇論文[9]。在時任主編西爾維斯特的邀請下，這篇論文被提交至《美國數學雜志》并正式發表，他還將論文預覽版寄給了科學期刊《自然》

Nature

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

N - E + R = 2。

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

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

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

將這些表達式代入歐拉公式，可得到計數公式：

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

因此，若不存在邊界邊數不超過五的區域，上式左邊將為負數，產生矛盾。

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

圖6 肯普鏈法示意圖

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

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

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

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

圖7 連接圖著色示意圖

（國家著色→描繪連接圖→頂點用顏色字母標記的示意圖）

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

Note on the preceding paper

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

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

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

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

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

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

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

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

Journal of Education

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

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

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

Map-colour theorem

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

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

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

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

圖11 希伍德的反例示意圖

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

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

圖12 帝國問題示意圖

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

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

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

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

圖13 希伍德對三次地圖交點的標記示意圖

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

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

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

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

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

20世紀的第一個新想法來自保羅·韋尼克（Paul Wernicke）。他于1866年出生在德國，獲得數學學位后，于1893年移民美國并成為美國公民。他在肯塔基州擔任現代語言教師，但主要興趣仍在數學領域，后來返回德國撰寫了一篇關于拓撲學的博士論文，之后再次回到美國。

韋尼克長期關注四色問題。在德國期間，他為《數學年刊》

Mathematische Annalen

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

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

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

圖15 環大小為14的構型示意圖

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

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

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

Annals of Mathematics

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

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

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

在題為《模方程在拓撲學中的應用》

An application of modular equations in analytic situs

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

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

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

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

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

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

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

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

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

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

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

伯克霍夫對色多項式的興趣貫穿一生，分別于1930年和1934年發表了相關論文。1930年的論文由哈斯勒·惠特尼（Hassler Whitney）整理——惠特尼后來成為拓撲學先驅，他關于四色問題的想法給伯克霍夫留下了深刻印象，并在伯克霍夫的指導下完成了題為《圖的著色》

The Coloring of Graphs

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

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

伯克霍夫系統地證明了：所有環大小為3或4的構型都是可約的；對于環大小為5的構型，除了單個五邊形外，其余都是可約的。

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

圖18 伯克霍夫菱形示意圖

在隨后的幾十年里，更多的可約構型被發現，數量最終達到數千種。

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

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

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

The Four Color Theorem

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

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

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

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

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

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

10. 海因里希·黑施（Heinrich Heesch）

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

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

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

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

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

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

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

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

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

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

圖21 黑施的地圖區域符號示意圖

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

11. 沃爾夫岡·哈肯（Wolfgang Haken）

沃爾夫岡·哈肯（Wolfgang Haken）于1928年出生在柏林，早年就對數學表現出濃厚興趣。15歲時，他被征召加入二戰防空部隊，同時繼續完成學業，并于1946年初畢業。當時，大多數德國大學不招收23歲以下的學生，但基爾大學是個例外，17歲的哈肯成為該校最年輕的學生。他在學年中期被錄取，攻讀數學、物理和哲學專業，直接進入第二學期的課程學習，沒有任何前期基礎，但他最終成功跟上了進度，并在后來將這一時期描述為“非常、非常令人興奮——對我來說，那是一段美好的時光”。

當時基爾大學只有一位活躍的數學教授——卡爾-海因里希·魏斯（Karl-Heinrich Weise）。魏斯是一位優秀的教師，1947年在拓撲學課程中，他提到了三個未解決的問題：結問題（knot problem）、龐加萊猜想（Poincaré conjecture）和四色問題。這三個問題后來都成為哈肯畢生研究的重要部分：他解決了結問題，為龐加萊猜想的研究做出了重大貢獻，并最終與肯尼斯·阿佩爾共同解決了四色問題。

在基爾大學，哈肯結識了海因里希·黑施，并參加了他關于四色問題的演講。當時哈肯對此理解不深，但后來回憶起，黑施提到需要系統研究約10000個特殊情況才能證明四色定理。這次演講在哈肯心中埋下了種子，并在數十年后開花結果。

1948年獲得學位后，哈肯在魏斯的指導下開始研究生階段的學習，于1953年完成了關于高維拓撲學的博士論文。隨后，他移居慕尼黑，在西門子公司的研發部門從事微波技術工作。

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

Acta Mathematica

上。

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

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

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

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

如前所述，對于環大小為6的伯克霍夫菱形，需要檢查31種不同的環區域著色方案。但隨著構型復雜度的增加，著色方案的數量會急劇增長——環大小每增加1，著色方案數量就會變為原來的4倍；對于環大小為14的構型，需要考慮的著色方案多達199271種。由于需要驗證的構型數量眾多，當時的計算機需要數千小時才能完成，這在當時看來是難以實現的。

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

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

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

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

“計算機專家告訴我，這樣的研究方式是不可行的。現在，我決定放棄。我認為，這是無需計算機就能達到的極限。”

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

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

“我認為沒有什么是計算機做不到的——有些事情只是需要更長時間而已。我們為什么不試一試呢？”

圖22 肯尼斯·阿佩爾（1932—2013）與沃爾夫岡·哈肯（1928—2022）

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

當阿佩爾和哈肯開始實踐這一想法時，計算機輸出的構型列表中存在大量重復項，但阿佩爾很快引入了一些簡單的修改，減少了重復。這迅速成為一個持續的實驗過程：阿佩爾和哈肯定期調整放電算法，改進計算機程序，以優化構型列表。

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

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

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

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

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

“經仔細驗證，四種顏色足夠。”（Modulo careful checking it appears that four colors suffice.）

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

圖23 證明公布后數學系的郵戳示意圖

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

13. 后續發展

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

1977年12月，阿佩爾和哈肯在《伊利諾伊數學期刊》

Illinois Journal of Mathematics

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

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

圖24 阿佩爾和哈肯的部分可約構型示意圖

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

The four color proof suffices

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

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

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

原文參考文獻

[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

小樂數學科普近期文章

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

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

置頂加星★

數學科普不迷路！