五色定理

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

證明

以下是對五色定理的證明^[1]。

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

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

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

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

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

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

綜上所述，${\displaystyle G}$能進行5-著色。