四色定理（英語：four color theorem）稱為四色地圖定理（英語：four color map theorem），是一個數學定理[1]：如果平面上劃出一些鄰接區域，那麼可以四種顏色來這些區域染色，使得每兩個鄰接區域染顏色[2][3]；另一個通俗説法是：每個無外飛地地圖可以不多於四種顏色來染色，而且會有兩個鄰接區域顏色。
稱為鄰接兩個區域是指它們有一段公共邊界，而不僅是一個公共交點。
例如右圖左下角圓形中，紅色部分和綠色部分是鄰接區域，而黃色部分和紅色部分則不是鄰接區域。
「是否只用四種顏色能所有地圖染色？」問題是南非數學家法蘭西斯·古德里1852年提出，稱為「四色問題」或「四色猜想」。
人們發現，要證明寬鬆一點「五色定理」（即「只用五種顏色能所有地圖染色」）很，但四色問題出人意料地困難。
有許多人發表四色問題證明或反例，但證實是錯誤。
1976年，數學家凱尼斯·阿佩爾和沃夫岡·哈肯藉助電子計算機首次得到一個完全證明，四色問題於成四色定理。
這是首個主要藉助計算機證明定理。
這個證明一開始並不為許多數學家接受，因為人認為這個證明無法用人手直接驗證。
儘管隨着計算機普及，數學界計算機輔助證明能接受，但有數學家希望能夠找到或助計算機證明。
四色定理通俗版本是：「任意一個無飛地地圖可以四種顏色染色，使得沒有兩個相鄰國家染顏色。
」作為一個數學定理，四色定理有着數學敍述。
最初染色問題是幾何學概念描述，版本則需要用到拓撲學概念來定義。
設有一平面或其一部分，分為重疊區域集合。
一個「地圖」為以下劃分方式[2]:44：
所謂有界區域，是指能夠一個和矩形覆蓋區域。
無界區域是不能這樣矩形覆蓋區域[2]:44。
每個區域相當於通俗説法中「國家」，而區域之間邊界（「國家」之間「國界線」）定義自交曲線，稱為曲線。
曲線是指一個[0, 1]映射到平面
R
2
{\displaystyle \mathbb {R} ^{2}}
函數
c
{\displaystyle c}
像集：
C
=
{
c
(
t
)
;
t
∈
[
0
,
1
]
}
{\displaystyle C=\{c(t);\quad t\in [0,1]\}}
，並且要滿足：
這説曲線自身相交（沒有「打結」地方）。
10月23日，弗雷德裏克他哥哥發現作為一個猜想老師德摩根提出。
可以看出，邊界定義地圖本質：
.mw-parser-output .templatequote{margin-top:0;overflow:hidden}.mw-parser-output .templatequote .templatequotecite{line-height:1em;text-align:left;padding-left:2em;margin-top:0}.mw-parser-output .templatequote .templatequotecite cite{font-size:small}
平面
R
2
{\displaystyle \mathbb {R} ^{2}}
中一張地圖是指個曲線集合：
L
=
{
C
1
,
C
2
,
⋯
,
C
m
}
,
m
∈
N
,
m
⩾
2
{\displaystyle {\mathcal {L}}=\{C_{1},C_{2},\cdots ,C_{m}\},\,m\in \mathbb {N} ,m\geqslant 2}
，其中
∀
1
⩽
i
⩽
m
,
C
i
=
{
c
i
(
t
)
;
t
∈
[
0
,
1
]
}
{\displaystyle \forall 1\leqslant i\leqslant m,\,C_{i}=\{c_{i}(t);\quad t\in [0,1]\}}
，
c
i
{\displaystyle c_{i}}
為[0, 1]映射到
R
2
{\displaystyle \mathbb {R} ^{2}}
函數。
並且任意
1 任意端點稱為頂點。 可以説，一張地圖是一個有界平面圖定義。 定義地圖和頂點後，設所有屬於邊或頂點點為中性點，其集合設為 N L = x C i , 1 {\displaystyle {\mathcal {N}}_{\mathcal {L}}=\{x;\,x\in C_{i},\,1\leqslant i\leqslant m\}} ，則 L {\displaystyle {\mathcal {L}}} 其餘點劃分為若干個道路開集。 用拓撲學語言來説，每個「國家」是 R 2 − N L {\displaystyle \mathbb {R} ^{2}-{\mathcal {N}}_{\mathcal {L}}} 一個子集。 或者説，取一個非中性點 x {\displaystyle x} ，所有能夠 x {\displaystyle x} ，一條含中性點弧到達點構成集合，一個國家。 這樣定義國家滿足之前説特性，只有一個無界國家。 要注意是這裡定義國家是沒有飛地[2]:64。
後可以定義染色。 假設使用到顏色編號 1 {\displaystyle 1,2,3,\cdots ,n} 號顏色，地圖染色是指一個地圖中國家映射到 { {\displaystyle \{1,2,3,\cdots ,n\}} 上函數。 一個可行.mw-parser-output .serif{font-family:Times,serif}n-染色方案是指使得相鄰國家對應顏色函數。 四色定理説：每個地圖存在可行4-染色方案[2]:43。
拓撲學版本四色問題闡述可以轉化抽象圖論版本。 這裡轉化指是一種對偶概念。 即一個地圖轉化圖論中一個無向平面圖。 來説，是地圖中每一個國家用其內部一個點代表，作為一個頂點。 如果兩個國家相鄰，兩個頂點之間一條線。 這樣得到圖是一個平面圖（會有兩條相交），而每個國家選取代表點無關。 四色定理可以敍述：可以四種顏色平面圖頂點染色，使得頂點顏色[2]:118-122。
要注意是，並非所有地圖可以轉化圖論中平面圖。 如果一個國家有飛地話，不能只一個點來代表一個國家。 另外，如果一個國家是「國中國」，那麼即便可以地圖其轉化平面圖，會造成討論上不便。 但是，「國中國」着色十分解決，因為它只有一個鄰國，只需它染成和鄰國顏色可以。 所以大部分有關四色問題討論中可以「國中國」情形。 地，只有兩個鄰國情形可以。 如果規定不能夠有四個或者以上國家有公共邊界，那麼地圖轉化成平面圖裡面，每個區域是三條圍成。 這樣地圖稱為地圖。 如果任何一個頂點連出三條，那麼稱其「三度圖」（trivalent map）。 可以證明，如果存在四色定理反例，那麼國家數反例是三度圖。 因此四色問題證明過程中，會假設地圖對應圖是三度圖[2]:127-128。
「只需要四種顏色地圖着色」最初是法蘭西斯·古德里1852年提出猜想。 法蘭西斯·古德里於1831年生於倫敦。 1850年，他倫敦大學學院完成他數學學士學位後，花兩年時間修得法學學士學位[2]:2-3。 1852年，古德里繪製英格蘭分郡地圖時，發現許多地圖需用四種顏色染色，能保證有相鄰邊界分區顏色。 他這個發現告訴他弟弟弗雷德裏克·古德里[4]:92。 弗雷德裏克這時正在倫敦大學學院讀數學，師法蘭西斯上學時老師奧古斯塔斯·德摩根[2]:2,5。 10月23日，弗雷德裏克他哥哥發現作為一個猜想老師德摩根提出。 德摩根此猜想，通信中這個問題愛爾蘭數學家威廉·哈密頓提出。 德摩根信如今保存都柏林三一學院中[2]:7。 德摩根熱情相反，哈密這個問題絲感興趣。 他三天後回信中告訴德摩根，他「不會嘗試解決這個四元顏色問題」[2]:5。
四色問題之所以能夠得到數學界關注，德摩根功不可沒。 他推動四色問題研究工作如此，以至於許多人認為德摩根才是提出這個猜想人。 德摩根接下來兩年裡嘗試數學家通信。 他1853年12月9日1854年6月24日寫信他以前老師威廉·魏巍爾以及魏巍爾妹夫羅伯特·萊斯利·艾里斯，討論四色問題。 1860年4月14日，德摩根《雅典娜雜誌》上發表對魏巍爾書書評，其中提到四色定理。 1854年古德里兄弟中一人同一本雜誌上發表過四色定理文章[2]:11。 儘管德摩根書評直到1876年才引起大規模注意，但其發表開始，有了影響。 美國邏輯學家、哲學家查爾斯·桑德斯·皮爾斯看到雜誌上文章後，哈佛大學數學學會投遞了一份嘗試性證明（非證明），對可能證明思路進行了探討[5]。
1878年6月13日，倫敦王家數學學會一次會議上，阿瑟·凱萊其他會者詢問，四色足夠地圖着色問題是否證明。 後，他問題寫了一篇短小論文，問題作了介紹和分析，投給英國王家地理學會，並於次年（1879年）學會會刊上發表[2]:13。 凱萊文章使得四色定理進入到數學家們視野中。 這一次，四色定理引起注意。 凱萊論文發表不到一年，一份「可能是四色問題錯誤證明」就出現了[2]:15[4]:94。
作出這個證明人是倫敦律師兼數學家阿爾弗雷德·佈雷·肯普（英語：Alfred Kempe）。 肯普曾是凱萊劍橋大學學生，之前因為聯動裝置模型方面工作而出名。 《》雜誌確認了他證明，於1879年7月17日登載「四色猜想得到證明」消息。 證明當時成立不到兩年，出名《美國數學雜誌》上發表[6]。 其中原因主要是創辦《美國數學雜誌》詹姆斯·約瑟夫·西爾維斯特是凱萊好友，因此肯普「應雜誌主編要求」，這篇有分量論文發表知名雜誌上[2]:15。
《美國數學雜誌》顧問編輯威廉·愛德華·斯多利這個問題[7]。 他肯普證明做了一些簡化，並加上多個肯普處理情況下證明，收錄再版時附錄裏。 1879年11月5日，約翰·霍普金斯大學科學協會一次會議上，這個版本證明首次公開。 皮爾斯當時約翰·霍普金斯大學任教，他出席了這次會議，並提出自己以前工作，12月另一次會議中提出他使用邏輯方法證明作出改進[2]:16。 ，數學界認為四色猜想完全解決[2]:16[4]:102。
1880年，物理學家彼得·古德里·泰特（英語：Peter Guthrie Tait）《愛丁堡皇家學會會刊》發表一個四色猜想證明，然而其中只是將四色問題進行了變形，依賴於肯普工作，並沒有實質證明[2]:20。
肯普證明是基於國家數目進行歸納法。 很能證明國家數4以內時四色定理成立。 肯普假設國家數目多於n時四色定理成立，他目的是證明n+1個國家構成地圖可以約化超過n個國家構成地圖，從而證明四色定理成立[6][8]。
肯普證明一個有關平面圖結論：任意地圖中存在一個國家（頂點），其鄰國數目於於5。 證明，圖論版本中，地圖轉換成平面圖。 而一個平面圖中，設V頂點數，E邊數，F區域數，於每個區域三條圍成，每條隔開兩個區域，所以區域數和邊數滿足：2E ≥ 3F。 設每個頂點有6條邊，那麼於每條應兩個頂點，所以頂點數和邊數滿足：2E ≥ 6V。 合起來有： 因此可能每個頂點有六條，説，有一個國家鄰國數目超過5[3]:177。 E.呂卡《娛樂數學》（Récréations mathématiques）第四卷提到肯普證明，但絲毫沒提到希伍德指出肯普證明錯處[4]:108[10]。 延伸閱讀… A國鄰國數目超過5個。 如果A國鄰國數目超過3個，那麼可以A國「去掉」（比如和其中一個鄰國連成），形成一個n個國家地圖，這個地圖可以4種顏色着色，而原來3個鄰國多用了3種顏色。 這時候A國「放回去」，染上第4種顏色，於找到給原地圖4-着色方法[8]。
這種能夠「去掉」一個國家，減少國家數局部後來稱為「可約構形」（reducible configuration）。 接下來肯A國有4個鄰國和5個鄰國情況是可約構形，於是能夠化為不多於n個國家情況。 因此任何n+1個國家地圖可以四種顏色染色，因而通過歸納法可知，四色定理成立[6]。
A國有4個鄰國時候，假如有兩個鄰國同色，那麼可以它們「作」同一個國家，和A國連成進行約化，而於此時這4個鄰國多用了3種顏色，所以可以A國「放回去」，染上第4種顏色。 假如4個鄰國色，不妨設為紅、黃、藍、綠（如右圖1）。 肯普思路是其轉化兩個鄰國同色情形，他採用方法後來稱為「肯普鏈」方法（Kempe chain）。 來説，肯普希望將其中一個鄰國顏色換成「面」顏色，比如色（圖1中綠1）換為紅色。 如果綠色鄰國沒有紅色鄰國，那麼換色沒有任何問題；如果它有紅色鄰國（圖1中紅1），那麼需要其紅色換成綠色，……如此換下去。 因此需要換色是一條綠－紅－綠－紅……「鏈條」，所謂「肯普鏈」。 如果對面紅色國家這個鏈條裏，那麼只需要將鏈中國家紅綠互換，能轉化成兩個鄰國同色情況（圖2）。 如果對面紅色國家鏈條裡面（如圖3），那麼紅綠互換沒有意義了。 但是這時候可以看到，紅綠「肯普鏈」A國形成一個圈，所以黃色鄰國和藍色鄰國有一個圈裡（圖3中是黃色鄰國）。 這樣圈外（藍色）鄰國「肯普鏈」圈內（黃色）鄰國沒有交集，於是其黃藍互換，能轉化成兩個鄰國同色情況。 這説A國4個鄰國構成可約構形[3]:178[6]。
於A國有5個鄰國構形，肯普使用肯普鏈換色方式來證明其可約性。 他使用了兩次換色，5種顏色降至3種，從而成為可約構形。 這是後來希伍德找出錯誤地方[6][8]。
四色猜想短短的兩年時間裡一個並非「專業」數學家「外行人」解決，讓很多當初認為這個問題是難題數學家覺得，這個問題並沒有涉及到數學中深層本質。 對四色問題研究減少，數學家們其視為事實。 劉易斯·卡羅爾四色問題化為遊戲：一方設計地圖，另一方來其着色[9]。 1886年，英國男校克里夫頓學院（英語：Clifton College）校長四色問題作為全校學生挑戰難題，要求答案長度「不得超過一頁紙文字，30行算式以及一頁紙圖」[4]:105。
德國數學家菲利克斯·克萊因這個問題和1840年莫比烏斯提出並解決另一個問題相混淆起來，認為四色問題不過是後者直接推論。 這個誤解幾何學家理查德·巴爾策（德語：Heinrich Richard Baltzer）1885年複，導致直到21世紀有類傳言[2]:21。 而實際上莫比烏斯解決是完全圖 K 5 {\displaystyle K_{5}} 不是平面圖問題，與四色問題沒有直接聯繫。
然而，肯普證明發表11年後，珀西·約翰·希伍德發表一篇文章，指出肯普證明中包含一個錯誤。 希伍德文章中地指出，他無法修正這個錯誤，得到一個四色問題正確證明，因此他文章是摧毀而非建設（rather destructive than constructive）[2]:22。 不過，儘管無法得到四色定理，希伍德肯普思路上前進，得到一個定理：五色定理。
希伍德的説，肯普錯誤於證明5鄰國是可約構形時，構造兩條肯普鏈換色，然而第二次換色時，肯普方法並。 希伍德提供一個包含25個國家地圖作為反例[4]:106。
希伍德報告是肯普自己提交倫敦皇家數學學會。 肯普承認自己證明中存在缺陷，並且他未能去除這個缺陷[4]:107。 然而希伍德工作並沒有受到應有重視。 數學界普遍認為這只是無關錯誤，能得到糾正。 1894年創刊《L’intermédiaire des mathématiciens》雜誌四色問題作為頭一個徵解問題，結果收到解答，稱其解決，並引用了肯普、泰特人論文。 E.呂卡《娛樂數學》（Récréations mathématiques）第四卷提到肯普證明，但絲毫沒提到希伍德指出肯普證明錯處[4]:108[10]。 延伸閱讀…
直到世紀交時，數學家們認為，四色問題需要只是某個靈光一現妙想。 一個流傳故事是閔可夫斯基教拓撲學課時提到四色問題，説：「這個問題沒有解決，只是因為試圖解決它是三流數學家」。 他聲稱要課上證明，但直到下課無法，耗費若干堂課時間後，只能承認失敗[11]:92。
20世紀起，歐洲數學界四色定理研究出現停滯。 相反地，這個問題美國得到關注。 傑出的數學家研究了這個問題，並作出貢獻。 一部分努力是修正肯普證明；另一方面努力是延續泰特思路，將四色問題進行轉化，使用多有力數學工具。
對四色問題轉化泰特後並停止過。 拓撲學版本轉化圖染色版本後，希伍德1898年提出變形。 肯普和泰特注意到，證明四色問題只需要考慮三個國家有「交點」情況，多國家有交點情形可以轉化前者。 因此這樣對應染色圖中，每個頂點會連出三條。 這樣圖稱為「三度圖」（trivalent map）。 希伍德觀察到，如果三度圖中任意圍成區域，個數是3倍數，那麼圖可以4-染色。 他進一步發現，只要存在一種圖頂點賦值+1或-1方法，使得每個區域頂點數字和3整除，那麼圖可以4-染色。 可以證明，4-染色和存在賦值方法是價[4]:159。
美國，數學家四色定理研究未停止過。 約翰·霍普金斯大學皮爾斯以及斯多利人外，另一個研究者是保羅·温尼克（英語：Paul Wernicke）。 當時學術聖地哥廷根大學畢業温尼克來到美國後肯塔基大學任教。 他1904年發表論文中出現了可約性雛形。 然而美國數學界四色問題上首次實質性進展出現在1912年後。 普林斯頓大學奧斯瓦爾德·維布倫（經濟學家託爾斯坦·範伯倫侄子）是這波浪潮先鋒。 他工作是拓撲學，1905年證明瞭若爾曲線定理[12]。 龐加萊發展出新代數工具有深入瞭解他，很地開始四色定理研究。 他使用幾何學觀念和域上關聯矩陣（英語：incidence matrix）作為工具[4]:160，將四色問題轉化成域係數空間上方程問題。 這個方向後來密碼學家、數學家威廉·託馬斯·塔特（英語：William Thomas Tutte）稱為「量化方法」（the quantitative method）。 同年，他普林斯頓同僚喬治·戴維·伯克霍夫開始探索這個方向，但一年後他開始轉向肯普方法，即是塔特所稱「定性方法」（the qualitative method），並提出可約環（reducible ring）概念[2]:25。 1913年，伯克霍夫發表名《地圖可約性》（The Reducibility of Maps）論文，利用可約環證瞭：超過12個國家構成地圖能四色染色。 1922年，伯克霍夫學生菲利普·富蘭克林（英語：Philip Franklin）運用方法，結論加強到：超過25個國家構成地圖能四色染色[4]:160[13][14]。 於別克霍夫首次證明四色定理超過12個國家地圖成立，歷史上證明可染色地圖國家數上限記錄稱為別克霍夫數[4]:167。
伯克霍夫人證明是肯普方法延續和系統化，歸納尋找一個不可避免可約構形集（an unavoidable set of reducible configurations）。 這個理念體現肯普證明中。 他説任一地圖中存在以下四種構形：2鄰國國家、3鄰國國家、4鄰國國家和5鄰國國家；然後證明每種構形是可約構形。 後來希爾這種分類方式稱為「不可避免集」。 伯克霍夫構想是使用反證法：反設存在需要五種顏色染色地圖，那麼其中存在國家數「五色地圖」（five-chromatic map）。 這個地圖是「不可」（irreducible）。 而只要找到一組構形，使五色地圖中不可避免地會出現其中一種構形，並且每個構形是可約，那麼能夠通過約化，地圖國家數減少，從而導致矛盾[4]:169。
肯普找不可避免集由四種構形組成，但他證明後一種（5鄰國國家）可約性，因此伯克霍夫開始尋找刻畫不可避免集新方法。 他提出相鄰國家連成環來整個地圖M分為三個部分：環內部分A、環外部分B以及環本身R。 若環上國家數n稱其n-環。 如果R任意染色不妨礙A進行染色，那麼可以「」A而M染色問題約化B+R染色問題。 這時稱A+R是可約構形，R稱為可約環。 伯克霍夫證明瞭：當R是4-環，或者R是5-環且A中國家不止一個，或者A+R是「伯克霍夫菱形」時，A+R是可約構形。 因此五色地圖可能包含這些構形[4]:169。 富蘭克林進一步證明：五色地圖中包含三個鄰接五邊國（5鄰國國家），或者鄰接兩個五邊國一個六邊國，或者鄰接一個五邊國和兩個六邊國。 他從而得出一系列可約構形，形成了25國以下地圖不可避免可約構形集。 因此推出，五色地圖包含26個國家[14]。
這種方法終極目標是找到所有地圖不可避免可約構形集。 然而國家數增多，要找到不可避免集並證明其可約化性。 這主要是因為環增大，染色方法數目會迅速增大。 6-環4-染色方法有31種，而12-環則有22144種。 因此大環圍成構形驗證可約性是十分工作。 1926年，C.N.Reynolds別克霍夫數25提高到27。 1938年，富蘭克林其推進到31。 1941年，C.E.Winn提高到35。 而直到1968年，別克霍夫數40[2]:185。
⩽
i
<
j
⩽
m
{\displaystyle 1\leqslant i
{
x
;
∈
⩽
i
⩽
m
}
,
2
,
3
,
⋯
,
n
1
,
2
,
3
,
⋯
,
n
}
但這圖論中歐拉公式：V + F = E + 2矛盾。
