四色定理（Four color theorem）又叫四色問題或四色猜想，是世界近代三大數學難題之一，其是指每個平面地圖都可以只用4種顏色來染色，而且沒有兩個鄰接的區域顏色相同。同時，在圖論語言中，也有對四色定理的陳述。
四色問題是英國數學家格色里（Guthrie）在1850年提出的。他的老師德摩根（De?Morgan）給出了這個問題的原始表述。隨后，很多數學家對該問題展開討論，肯普在美國數學雜志中的證明引發了數學界的轟動，但后來，有人舉出了反例，他的證明并未成功。直到1976年，肯尼思·阿佩爾（Kenneth Appel）和沃卡岡·哈肯（Wolfgang Haken）在肯普證明的基礎上借助計算機證明了四色定理。
四色定理為利用計算機進行證明的數學定理，為數學的研究開辟了新的途徑。在定理研究過程中，有不少新理論、新思想誕生，所引進的概念與方法刺激了拓撲學與圖論的生長、發展。此外，在實際生活中、地圖著色問題、日程表編排問題、印刷電路板分層問題也和四色定理密切相關。
定理內容
語言陳述
四色定理的通俗的說法是，每個平面地圖都可以只用4種顏色來染色，而且沒有兩個鄰接的區域顏色相同。
圖論陳述
平面中面的染色（face-k-coloring），是指種顏色對中面的一種分配，使得公共邊的兩個面顏色不同。換言之，中面的k染色是映射使得對每個 ，中任何兩個面無公共邊，記。若平圖中的面存在k染色，則稱中面色可染（face-k-colorable）。參數被稱為的面色數（face chromatic number）。例如。
四色問題即為：為對任何平圖，是否有。
簡史
1850年，英國數學家格色里（Guthrie）（在倫敦學法律）注意到大多數地圖使用4種顏色即可上色，但不知道是否對所有的地圖都正確。他就把這個問題提給了他的老師德摩根（De Morgan）。德摩根對這個問題也不能給出答案，1852年，他把該問題以書信的形式提給了漢密爾頓（Hamilton），但漢密爾頓回答說沒有時間考慮這個問題。
1860年，帕斯（Piece）試圖證明該猜想，但是失敗了。1878年，凱利（Cayley）聽到這個問題，他在1879發表了題為《關于地圖的著色》（《On the coloring of maps》）的文章，在文章中，他解釋了該問題證明的難處。
1878～1880年間，肯普（Kempe）和泰勒（Tait）分別提交了證明四色猜想的論文，宣布證明了四色猜想。他的證明在數學界引起了轟動，并因此成為皇家科學家并得到授勛。他的方法一直被沿用。1890年，希伍德（Heawood）發現肯普關于“沒有極小五色地圖能有一國具有五個鄰國”的證明理由有破綻。不久泰勒的證明也被人們否定了，人們發現他們（肯普和泰勒）的方法雖然不能證明地圖著色用4種顏色，但可以證明5種顏色就夠了(五色定理)。1898年，希伍德證明了地圖上每個區域的邊數是3的倍數時，四色定理成立。這以后，人們開始考慮通過限制地圖的區域來證明四色定理。
1922年，富蘭克林（Franklin）證明了最多有25個區域的地圖是四面可著色的。1976年，牧野（Muyer）證明了最多有90個區域的地圖的四色問題。1976年，美國伊利諾伊州大學的肯尼思·阿佩爾（Kenneth Appel）和沃卡岡·哈肯（Wolfgang Haken）把四色問題歸結為2000個不同的組合結構圖形，利用三臺高速IBM360計算機對這些圖形進行分析，用了1200機時，近百億次邏輯判斷，證明了“四色定理”。1977年，證明的細節發表在文章上，爭議也從此開始。爭議的中心是人們能不能、該不該接受這個證明。1996年，羅伯森（Robertson），桑德爾（Samders），西摩爾（Seymour），托馬斯（Thomas）給出另一個機器證明。他們利用了更有效的方法，使用時減到633小時。
證明
肯普證明
肯普用圖論的知識對于四色猜想進行了證明，首先需引入如下基礎概念。
每個有界面的度都為3的平面被稱為構形。如圖1所示四個平面都是構形，分別記為。
設是由有限個構形組成的集。若任何三角剖分圖至少含中一個構形，則稱是不可免完備集。由于任何平面的最小度不超過5，所以是不可免完備集。
一個構形被稱為可約的，如果它不含在任何一個最小圖中。
若四色猜想不成立，那么必存在一些5色平圖，其中階數最小的被稱為最小圖。
肯普是通過證明最小圖不存在來證明四色猜想的，證明過程如下。
反證：設是最小圖，則是三角剖分圖。因此，必須含中的構形，若含或，則
。令是中點的4染色，則至多只需三種顏色，矛盾于，所以不含構形和。
設含構形，且，是中的4染色，并不妨設，其中顏色標在該點上，則在中和在中不同時都是連通的，否則，中路和中路會相交，如下圖所示：
不妨設和在中不連通。于是，交換中含連通分支中點的顏色，被染上顏色4，而的顏色不變。空出顏色1來染點，即，矛盾于，所以不含。
肯普采用同樣的方法證明也不含構形。于是三角剖分圖不含中任何一個構形，矛盾于是不可免完備集，從而證明了最小圖不存在，即四色猜想得證。
計算機證明
高速數字計算機的發明，促使更多數學家對“四色問題”進行研究。從1936年就開始研究四色猜想的海克，公開宣稱四色猜想可用尋找可約圖形的不可避免組來證明。他的學生丟雷寫了一個計算程序，海克不僅能用這程序產生的數據來證明構形可約，而且描繪可約構形的方法是從改造地圖成為數學上稱為“對偶”形著手。
自從“可用尋找可約構形不可避免組的方法來證明四色猜想”這一猜想提出后，人們沿著這一思考路線采用各種方法來尋求可約構形的不可避免組。后來，這一猜想的提出者希什（Hish）運用移植手段，將物理學上一種在電網絡中國移動通信集團電荷的“放電法”應用到這一問題的探討之中，即用“放電法”來尋求構形的不可避免組。這種方法雖然很初步，尚待完善，但卻為后來證明四色猜想奠定了良好的基礎。
20世紀70年代初，美國數學家赫爾曼·哈肯試圖以改良了的放電方法來證明四色猜想。但是，他遇到了困難：可約構形的任何一個不可避免組都可能有很大的構形，其計算量十分巨大。后來，他逐步認識到，用人工方法是無法完成這一巨大工作量的。于是，他便開始尋求新手段，從數學之外來選擇新工具，并自然聯想到具有極大計算能力的高速電子計算機。比如，哈肯于1972年就作出了“肯定不會對四色猜想給出一個非機器證明”的結論。即只有在方法上實行革命性的變革，運用現代技術成果——電子計算機這個有效工具，即采取機器證明的方法，四色猜想才可能獲得最后解決。
1972年，阿佩爾與哈肯設計了一個新的計算程序。這個程序不僅能作出特殊類型的放電過程，而且還能給出從最重要的情況得出的構形作為輸出。經過實際計算和不斷修改得到了一個可行的程序，并通過它證明了地圖上可約構形的不可避免組的存在性。后來，他們又經過不斷修改程序，反復實驗，改進放電過程，并于1976年1月6日通過電子計算機找到了可約構形的不可避免組，從而完成了四色猜想的證明，最終獲得了?“四色定理”。
在計算機證明過程中，阿佩爾和哈肯構造了1478個構形，后來羅伯森、桑德爾、西摩爾、托馬斯等人將構型減少到633個，但對于人來說，證明633個構型是可約的仍然是一個困難的問題。
推廣
三色圖
例如：設圖中每個頂點都是三次的，每個區域圖都有偶數條邊和偶數個頂點，且每條邊上都有一個區域圖相鄰，則此平面可用三種顏色染色，即
和
證明：肯普的證明方法是利用一個多區域圖（子圖）的組合構形圖來進行文字敘述證明的，如下圖
從上圖中可以看出，題中所設定的每個頂點上的次數為和每個區域圖都有偶數條邊及偶數個頂點，且每條邊上都有一個區域圖相鄰的條件成立。在對整個圖染色時沒有超過三種顏色，同時，又滿足了在區域圖上相鄰的每條邊上都染上了一種顏色，由此形成了整個圖中每個頂點上都染上了不同的顏色和相鄰在每條邊上的兩個面都染上了不同的顏色。
五色圖
五色定理：用5種顏色可以給任意簡單連通平面圖正常著色。
證明：對圖的頂點數作歸納。
（1）當時，顯然成立。
（2）假設個頂點時成立，下面考慮階簡單連通平面圖。
由定理在簡單連通平面圖中至少有一個頂點，其次數可知，圖G至少存在一個頂點，其次數。顯然是階簡單連通平面圖，由歸納假設可用5種顏色進行著色。
假設已用紅、黃、藍、綠、黑5種顏色對著好了色，現在考慮對中頂點進行著色。
1）若，顯然可用它的鄰接頂點所著顏色之外的一種顏色對進行著色，即可以用5種顏色著色。
2）若，顯然只需考慮與鄰接的頂點被著以不同的5種顏色的情況進行討論。
令，，考慮導致的的導出子圖。
a）若和分別屬于的不同連通分圖，那么將所在分圖的紅藍色對調，并不影響圖的正常著色。然后將著上紅色，即得圖的正常著色。
b）若和屬于同一分圖中，則和之間必有一條頂點屬于紅藍集的路徑，它加上可構成回路。
由于的存在，將黃綠集分為兩個子集，一個在內，另一個在外，于是黃綠集的導出子圖至少有兩個分圖，一個在內，一個在外。于是問題轉化為a)的類型，對黃綠集按a)的辦法進行處理，即得圖的正常著色，證畢。
無限圖
構造一個具有無限色數的局部有限可數圖。
解：只需取是所有的并集，其中是所有正整數。
注：如果希望圖是連通的，那么將的一個頂點與的一個頂點相連，的一個頂點與的一個頂點相連，依此類推。
例1：如果一個無限圖連通并且局部有限，其所有頂點的度數是偶數，那么它是否必須包含雙向無線的歐拉步道（即頂點序列使得是一條邊，并且圖中的每條邊恰好出現一次）。
解：否。取反例為有共同起點的四個不同路徑組成的圖。
例2：證明在頂點存在一個可數圖，其中。
證明：歸納構造這個圖，首先連接，于是達到要求，剩余的頂點的度數為0或1。假設已經得到一個圖，使得個頂點的度數達到要求，其余頂點的度數為0或1，將連接到所需個數的度數為0的頂點，則，接下來面對的就是個頂點到達要求的情況。最終，任何兩個頂點的連接方式確定，得到了所需的可數圖。
應用
地圖著色
在任何一張地圖上，總能用四種顏色給各個國家著色，使得鄰國的顏色不同。這里的地圖不包含那種稀奇的故意找別扭的“人造地圖”。比方世界是一個圓，從圓的中心作條半徑，將圓分成個國家，則個國家均為相鄰于圓心的鄰國，于是要做到鄰國的顏色不同，就要用種顏色了。這里的鄰國是有共同邊界線（不是有限個點）的連通區域，滿足這個條件的區域被稱為“構形”，如此形成的地圖被稱為正規地圖。在正規地圖中，沒有三個以上的區域相交于一點，并且沒有一個區域完全包圍另一區域。世界上絕大多數的地圖都是正規的。
日程表的編排
一些日程表編排問題也可以看成四色問題，例如，每逢學期結束，學校總要安排期終考試。尤其在實行學分制的大學里，考試日程表的編排是很有講究的，既要做到日程安排緊湊有序，又要杜絕某生選修的兩門課程同一時間考試的情況出現。設想個學生構成點集，門課構成點集，學生選課程，則在之間以線相連，這樣便組成一個偶圖。給中的邊染上各種顏色，顏色相同的邊所對應的課程在同一時間考試。接下來考慮的問題就是選用盡可能少的顏色，使得從中同一點出發的邊具有不同的顏色。此外，四色問題在有效地設計航空班機日程表方面也起到了推動作用。
印刷電路板分層
印刷電路板的分層問題也是四色問題的應用。將四色圖的邊對應于導線，頂點對應于接點，沒有導線連接的兩個接點間可能要裝配元件。
參考資料 >