五色定理

五色定理是圖論中的一個結論：將一個平面分成若干區域，給這些區域染色，且保證任意相鄰區域沒有相同顏色，那麼所需顏色不超過五種。五色定理比四色定理弱，也比四色定理更容易證明。1879年，阿爾弗雷德·布雷·肯普給出了四色定理的一個證明，當時為人所接受，但11年後，珀西·約翰·希伍德卻發現了肯普的證明中存在錯誤，他把肯普的證明加以修改，得到了五色定理。

證明

以下是對五色定理的證明。

給定$n$階平面圖$G$，我們對$G$的階數進行歸納證明。

當$n\leq 5$時，正確性顯然。

假設$n\geq 6$且對於任意的$n-1$階平面圖該結論成立。因為$G$是平面圖，那麼存在點$v\in V(G)$，滿足$d(v)\leq 5$（通過歐拉公式可知對任意平面圖$G$，$\delta (G)\leq 5$）。

考慮圖$G':=G-v$。因為$|G'|=n-1$，由歸納假設知$G'$能進行5-着色。假設$G'$使用$1,2,3,4,5$五種顏色着色。考慮$v$的相鄰點，如果在$G'$中它們用了不到五種顏色着色，那麼我們從剩下的顏色中選一個為$v$着色，就得到了$G$的一個5-着色方式。如果在$G'$中它們用上了所有五種顏色，這就意味着$v$有且僅有5個相鄰點（$d(v)\leq 5$），從順時針方向我們依次稱它們為$w_{1},w_{2},w_{3},w_{4},w_{5}$，不失一般性，假設$w_{i}$的顏色為$i$。

我們希望通過調整$G'$的着色方式，使得$v$有色可染。考慮$G'$中所有顏色為$1$或$3$的點。

1. 如果$G'$中不存在這樣一條連接$w_{1}$與$w_{3}$的路徑，路徑上所有點的顏色均為$1$或$3$。定義$H\subseteq G'$是滿足以下條件的所有路徑的併集：以$w_{1}$為起點且路徑上所有點的顏色均為$1$或$3$。注意到$(w_{3}\cup N(w_{3}))\cap V(H)=\emptyset$。此時我們可以將$H$中所有點的顏色互換：把$3$換成$1$，把$1$換成$3$。交換之後也是$G'$的一個5-着色方式。此時$w_{1}$的顏色變成了$3$，我們將$v$染為$1$。因此，$G$能進行5-着色。
2. 如果$G'$中存在這樣一條連接$w_{1}$與$w_{3}$的路徑，路徑上所有點的顏色均為$1$或$3$，我們稱之為$P$。注意到$P$與$v$共同形成了一個環，這個環要麼把$w_{2}$要麼把$w_{4}$圈在裏面。此時我們發現，不存在這樣一條連接$w_{2}$與$w_{4}$的路徑，路徑上所有點的顏色均為$2$或$4$。我們只需按照情況1中的方式調整顏色即可。因此，$G$能進行5-着色。

綜上所述，$G$能進行5-着色。

參考資料

• Heawood, P. J., Map-Colour Theorems, Quarterly Journal of Mathematics, Oxford 24, 1890, 24: 332–338