畫地圖（媽媽看得懂的數學證明）

(image from Wikipedia)
前陣子，「四色定理」因故在某數學討論板引起一陣騷動。相當懷念幾何的我，在此淺談相關知識，藉以討一些溫存。:)

四色定理：為任意地圖著色時，最多只需要用到四種顏色，就可以確保每個相鄰國家不同色。（註：一、「相鄰」是指擁有同邊界，不只是同點。二、假設飛地不需與所屬國同色。）

證明四色定理：嗯，證不出來。四色定理的證明必須用電腦寫程式去跑，將無限多種地圖先縮減為上千或上百種，然後，每一種都去檢驗。

於是，鬆一點，來談五色定理：五色就夠確保相鄰國家不同色。它有相當的重要性，因為四色定理的電腦證明比須依賴五色定理的成立（並運用反證法）。我們可用歐拉公式來證明五色定理。

歐拉公式：一個連通平面圖有 v 個點、 e 個邊、與 f 個面，則
v - e + f = 2。



上面都是連通平面圖。(a) 是一棵樹，每邊像樹枝一樣從交點發展出去。(b) 上部三個邊連成一圈，這輩子沒見過這種樹枝，所以它不是樹。(c) 是一張正規地圖，不會有像前兩圖裡的樹枝末梢點；(c) 有 5 個面，注意：想像連通平面圖為球面戳一洞後延展攤平，故圖形外面也算一面。

證明歐拉公式：對邊數 e 作數學歸納法。

將該連通平面圖稱為 G 。e = 0 時，G 就只有一個點、一個面，所以公式 v - e + f =2 成立。
假設 e = k 時公式成立，以下證明 e = k + 1 時也會成立。

若 G 是樹林，設 b 是 G 的一個末梢點，
則 G' = G - b（移去一個末梢點也會跟著移去一個邊）仍是樹，所以也是一種連通平面圖，
→ G' 的 e' = e - 1 = k, v' = v - 1, f' = f; v' - e' + f' =2
所以 v - e + f = (v' + 1) - (e' + 1) + f' = 2

若 G 不是樹林，設 c 是 G 的某圈的某邊，
則 G' = G - c（某圈面失邊破防）仍是連通平面圖，
→ e' = e - 1 = k, v' = v, f' = f - 1; v' - e' + f' =2
所以 v - e + f = v' - (e'+1) + (f' +1) = 2

得證。

接下來嘗試證明五色定理。過程中我們只須考慮每交點只有三國相遇的球面地圖。下面左圖為某球面地圖展平：一、如果某點有四國以上相遇，我們可以在那點放上一個新國（如下中圖），新地圖就變成每點只有三國相遇。若新地圖有解，原地圖就一定有解（因為只要在著好色後把新國刪除就好了）。至於某小國單獨座落在某大國內的情形很容易著色，也不必考慮。二、再來，我們可將每個國家對應成一點，依國家相鄰狀況將點相連，於是成為非常簡單的三角形拼圖（如下右圖）。



首先用歐拉公式證明「至少有一國其相鄰國家小於等於五個」，即三角形拼圖中「至少有一點，其與之相連的點小於等於五個」：

假設共有 v 個點，f 個面，e 個邊；其中與 i 個點相連的點共有 v_i 個。則

v = v₂ + v₃ + v₄ + …… (式1)

每面有三邊（因為統統是三角形），而每邊有兩面，故 3f = 2e。與歐拉公式 v - e + f = 2 聯立得

6v - 2e= 12 (式2)

另外，與 i 個點相連的點也被 i 個面包圍， 故總面數的三倍（因為一面有三點，所以用點來數面會重複數到三次）為

3f = 2e = 2v₂ + 3v₃ + 4v₄+…… (式3)

將 (1) (3) 代入 (2) 得

為了使左式為正數，至少要有一個 i 小於 6，意即：至少有一個點（國家），其相連點數（相鄰國家數）小於等於 5。得證。

最後可對國家數 v 作數學歸納法以完成「五色定理」的證明。設 v < k 時定理成立，討論 v = k 的情形，選擇性移去邊界減少一個（或兩個）國家數，之後再補回去。討論須分成 v₂ ≠ 0，v₃ ≠ 0，v₄ ≠ 0，v₅ ≠ 0 等情況，各情況又可能出現跳隔的鄰國為不同國或同國的情形。細心討論之後可以發現五色足夠。以下首舉最簡單的 v₂ ≠ 0 的情形。

若 v₂ ≠ 0 ，代表至少有一國（稱它為 C ）只受兩國（稱它們為 A、B ）包圍，此情況可移去 C、B 邊界而化為共只有 v -1 國的地圖，於是新圖五色定理成立。著色後再將原來移走的邊界還原。由於 A、B 兩國只用去兩色，我們可以將 C 國著以剩下三色中的任何一色。

第二個討論 v₂ = 0 但 v₃ ≠ 0 的情形。然後以此類推討論下去。


標題寫「媽媽看得懂」，是因為當初數學討論板有人如此描述自己的文章。於是我自然當仁不讓（？），更何況我媽是天才。