一、采用三度正大平麵區域圖
本證明對象的原型采用三度正則,即每個頂點關聯3個弧——邊界線的區域圖形。在區域圖形中能證明四色定理,就在一切區域圖形中證明了四色定理。
使前麵的芯區域之頂點擴改為色區,變為區域圖形,原4個區域的相鄰關係和填色並不因之有任何改變。所以不同的是,原來兩個入色區和兩個色區交接於頂點,色區與色區相接,但均無相鄰的邊界線,互不影響填色。因此,將頂點擴改為色區後,雖使色區與色區互不相接,但對原四個的填色與證明四色定理來說,全然無礙。頂點擴改為色區能證明四色定理,色區縮變為頂點後同樣能證明四色定理成立。這也就是說區域數時四色定理成立,四色定理當然也成立。
二、在平麵區域圖中,一定有一個區域至多隻能同5個區域相鄰
用歐拉定理可以證明,任何一個區域性平麵圖中,一定有一個區域至多隻能同5個區域相鄰,由此找到證明四色定理的突破口。
根據歐拉所發現的平麵圖的歐拉公式,頂點、麵三個數的關係式在區域性平麵圖中,由於每個弧有兩個頂點,因而圖中共有2個頂點,又由於每個頂點在圖形中均為3個弧頂的點,每個頂點被數3次,因此:將歐拉公式兩邊乘以3,然後將2代入。
假定圖中每個區域同區域相鄰(即有N個弧),由於每個孤的兩邊為兩個區域(每個孤為相鄰兩個區域的共同邊界,被數2次,由此可以得出結論,即在圖中不可能每個區域至少同5個這域相鄰,一定有一個區域最多隻能同其他5個區域相鄰。
三、對區域數采用數學歸納法
在證明上,我們對采用數學歸納法。平麵區域圖中,隻有4個區域或少於4個區域的,顯然在填色上隻需4色就足夠了,不需要第五色。現在假設有一個區域的平麵圖,而我們已知所有區域是1個區域的平麵圖隻需4色。如能證明:區域數是1時四色定理成立,2時四色定理亦同樣成立那麼,我們就證明了四色定理。
根據前麵的證明,我們知道在任何區域性平麵圖中,必有一個區域X其鄰區,即最多隻能間他5個區域相鄰。已知四色定理成立,即圖中除區以外其他各區域共有四色,X區為待填色,尚此,在要證明四色定理,必須在任何情況下能使X區所填色為四色中的一色。如果在任何情況下,都能將四色中的一色填入X區,我們就可以借助數學歸納法把四色定理證明了。
四、對X區有4個鄰區或少於4個鄰區的平麵區域圖四色夠用的證明
如果X區隻有1個、2個或3個鄰區,直接對X區填上其鄰區尚未用過的四色中的一色即可。困難在於X區有4個鄰區特別是有5個鄰區時,怎樣才能在任何情況下都填進四色中的一色而又不與其鄰區的填色相同。
對有4個鄰區的X區,如其鄰區隻填有二色或三色,則直接填上其鄰區未用過的四色中的一色。如果4個鄰區已分別填上四種顏色,則需在保證區域圖無任何兩個鄰區填同一顏色的前提下,調整X區的鄰區的填色,使這4個鄰區共使用三色,而在X區填進四色中的另一色。這是一定可以做到的。希伍德在證明五色定理時已經用到這種方法。證明如下:
任取X區的鄰區填八色同與其不相鄰的X區的另一鄰區填色,從八區開始進行二色互換調節,即八區改填色,與其相鄰的填色的區域改填八色,直至整個圖的四色協調平衡(即無任何相鄰區域填相同顏色)。如果X區的鄰區在二色互換調節中不被涉及(即不屬於同一個色係,也就是說不是一個支),仍維持原填的色不變,由於X區的原填八色的鄰區已改填色,則X區可填進八色。如果X區的鄰區被二色互換調節涉及(即屬於同一個人一色係,也就是說是一個支),則X區的鄰區與其外相連的填二色的諸區域,必定同X區形成一封閉形二色圈。於是可在這個二色圈內,從X區的鄰區8(原填8色)或0(原填0色)開始,依次進行8、0二色互換調節而決不會涉及X區的另一鄰區0或8。因而八色線路截然分隔開來,分屬兩個色係。這樣,便使X區的鄰區隻填有三色,然後在X區填進四色中的另一色。
其他二色線路也這樣。對此,我們在後麵均用簡記法,它既可以表示兩個區直接相鄰,也可以表示中間還有一個填這兩種顏色並互相連接的區域。