五色定理

五色定理是圖論中的一個結論：將一個平面分成若干區域，給這些區域染色，且保證任意相鄰區域沒有相同顏色，那么所需顏色不超過五種。

五色定理是比四色定理弱的定理，但是比四色定理更容易證明。1879年，阿爾弗雷德·布雷·肯普給出了四色定理的一個證明，當時為人所接受，但11年後，珀西·約翰·希伍德卻發現了肯普的證明中存在錯誤，他把肯普的證明加以修改，得到了五色定理。

基本介紹

• 中文名：五色定理
• 外文名：five-color theorem
• 領域：圖論
• 相關定理：四色定理
• 提出者：珀西·約翰·希伍德
• 提出時間：1890年

背景及簡介

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

圖1 普肯的證明

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

圖2

從此人們把圖分為可約圖和不可約圖，可約圖是 4- 色的，不可約圖是 5- 色的，即不可約圖有 3 個特徵：（1）圖是最大平面圖；（2）圖是 5-色的頂點著色法；（3）圖是臨界的收縮。希伍德的“反例”就是不可約圖。希伍德的反例和他的“五色定理”的存在，使人們產生了誤解中的“四色猜想”，即只證可約圖（平面地圖），而不證不可約圖（球面地圖），一直流傳至今。誰也不敢反對它，把它視為真理。這樣一來的100 多年，徹底解決“四色猜想”的研究，就被希伍德的“反例”和他的“五色定理”占了統治地位。儘管世界上一些數學家仍然孜孜不倦地致力尋求徹底解決“四色猜想”的研究，就是 1976 年和 1996 年美國多位學者驗證的“四色猜想”只有可約圖，而沒有不可約圖。所以都超不出希伍德的“反例”和“五色定理”的範圍。

希伍德證明的“五色定理”

希伍德證明“五色定理”如下：“不妨設五種顏色是紅，白，黃，黑，藍。對頂點數用數學歸納法來證明。當頂點數 V=1、2、3、4、5 時，定理顯然成立。設頂點數 V=K （K ≥6）時定理也成立，我們考察 V=K+1時的情形。由引理，在這個平面圖中存在一個頂點 v ，它的度數小於或等於 5。現在我們將此頂點 v 除去，剩下來的是一個頂點數為 K 的平面圖，由數學歸納法的假設，可以用紅，白，黃，黑，藍五種顏色將它（即除去 v的圖）塗好。然後再把v點加進去，看看 V 應該塗哪種顏色才好”……就這樣，希伍德證明了，當頂點 V=K+1（V ≤ 5 度）時，“五色定理”成立，從而宣告“五色定理”證明成功。

圖3

希伍德用肯普鏈證明如下：“用字母 b、r、y、g 表示四種顏色，一條從 V1 到 Vn 的其點交錯地著有顏色 r 和 g 的通路稱為一條從 V1 到 Vn 的r- g 鏈。

圖4

（1）如圖 3所示，有一條從 2 到 4 的 b- g 鏈，也有一條從 2 到 5 的 b- y 鏈，因此在任一條鏈上交換顏色都不能空出一種顏色給 V。

（2）如圖 4所示，沒有從 1 到 4 的 r- g 鏈。因此可以沿 r- g 鏈從1 開始交換r 和g（括弧中的顏色）。

（3）如圖 5所示，但這空不出 r 給 V，因為與 V 相鄰的 3也是著r 色。

（4）如圖 6，顯然這可以變到一個 y，但如果我們試圖這樣從 3 開始沿 r- y 鏈交換 y 和 r。

（5）如圖 7所示，那么 6 和 7 都變成 r。這樣就可能使得即使每次交換移動一個 r，但仍不能同時移去兩個 r"。

圖5

從以上希伍德的證明可得出結論：希伍德證明不下去了。它不能空出一種顏色給 V，V只能著第五種顏色。因此反例是 5- 色的。

圖6

圖7

希伍德在證明“反例”上的重大錯誤

由於希伍德沒有看出：“當交換 r- g 後，已經破壞了從 2到4 的b- g 鏈，如圖5，而形成新的從 3 到 5 的 r- y 鏈。”如圖 8。所以當他試圖再交換 r- y 鏈而沒有經過 7點時，當然出現 6 和 7 都變成 r。如圖 7，如果經過 7 點繼續交換下去，也不能空出一種顏色給 V，如圖 9。以上就是希伍德在證明反例上有重大錯誤的秘密。所以說希伍德的證明是錯誤的。

圖8

圖9

希伍德證明存在的問題

數學歸納法與希伍德證明

數學歸納法是用來證明那些無窮大又與自然數 n 有關的數學命題，即n ∈ N。因為自然數 n是具有遞推的規律。所以與自然數 n 有關的數學命題可以歸納為兩個步驟：（1 ）證明當 n取第一個值 n0（例如 n0=1 或 2 等）時結論正確；（2）假設當 n=k（k ∈ N，且 k≥ n0）時結論正確，證明當n=k+1時，結論也正確。因此就能證明數學命題從 1 開始的所有自然數 n都成立。

希伍德企圖以自然數代替頂點數用數學歸納法來證明“五色定理”成立，那是不可能的。因為希伍德證明的數學命題是與頂點數 V （變數）有關的“五色定理。頂點數 V 是一個沒有規律的“變數”，它不具備像自然數一樣的遞推規律。所以與頂點數V（變數）有關的數學命題不可以歸納為兩個步驟來證明。因此“五色定理”不能對頂點數（變數）用數學歸納法來證明。

錯誤

希伍德對頂點數用數學歸納法來證明“五色定理”有以下幾個原則性的錯誤：

（1）在圖中各頂點不同，度數不同，因為度數是一個“變數”，所以各頂點也是“變數”，也就是說頂點數 V 是一個“變數”，而 n 是一個自然數。自然數 n 與頂點數 V 是兩個不同的概念，不能混淆，因此自然數不能代替頂點數（變數）。而希伍德卻以自然數代替頂點數，不考慮頂點的度數是“變數”，混淆了“變數”與“自然數”的概念，從而犯下了基本概念的錯誤。

（2）數學歸納法兩個步驟的第一步是遞推的基礎；第二步是遞推的依據，兩者缺一不可。希伍德在證明“五色定理”的第二步驟中：(1)“設頂點數 V（變數）=k（迴避k N，k ≥6）時，‘五色定理’成立”是沒有根據的，（2）當頂點數 V=K+1（有意選用 V ≤ 5 度的頂點而迴避V≥6度的頂點）時，“五色定理”成立。所以 V ≤ 5 度的頂點可以遞推，而 V ≥ 6 度的頂點就不可以遞推。因為 V>=6 度的頂點與 V ≤5 度的頂點的度數範圍不同，它們遞推的依據也不同，所以第二步就不是V ≥ 6 度的頂點的遞推依據，V ≥ 6 度的頂點就沒有遞推依據，無法遞推，“五色定理” 就無法成立。如圖 10：第二步中，當頂點數 V=K+1（V ≤ 5 度）時“五色定理”成立。但當 V = K + 2（V=7 度）時，它與頂點 V ≤ 5 度的度數範圍不同，所以第二步不是它的遞推依據，它就沒有遞推依據，它無法遞推，“五色定理”無法成立。因此希伍德在證明“五色定理” 的第二步驟中，因沒有考慮 V ≥ 6 度的頂點（變數）沒有遞推依據就無法遞推，而使“五色定理” 無法成立。這在邏輯推理上犯了不足為據的錯誤。

圖10

（3）過程中：(1)根據數學歸納法的理論，希伍德提出對頂點數用數學歸納法來證明“五色定理”成立，就必須滿足圖中的每一個頂點（變數）“五色定理”都成立。(2)而希伍德只用 V ≤ 5度的頂點，作為第 K+1 個頂點來證明“五色定理”成立，而沒有證明圖中 V≥ 6 度的頂點“五色定理”成立，就宣告成功。可看出(1 )和(2)相互矛盾。這種企圖以 V ≤ 5 度的頂點代表所有度數的頂點，在邏輯推理上犯了“以偏概全”、“以局代整”的錯誤。根據數學歸納法只能用來證明與自然數有關的數學命題，它不能用來證明與自然數無關的數學命題。而希伍德卻提出對頂點數(變數)，套用數學歸納法的格式來證明與自然數無關的數學命題“五色定理”，這種證明的方法，是完全錯誤的。希伍德證明的“五色定理” 根本站不住腳。根據推翻的定義：根本否定已有（希伍德證明了“五色定理”）的說法，當然希伍德的“五色定理”也就被推翻了。