同五色定理證明的歸納法
記l[i,j]表示i色和j色交替出現的一條路。
記g[i,j]表示由著i色和j色的頂點的匯出子圖。
對頂點n做歸納。
1. 當n<=4時，顯然可四色著圖。
2. 假設當n=k時，可四色著圖。於是當n=k+1時，記圖中的乙個＜=5度的頂點為v。，去掉v。，則剩餘k個頂點，根據歸納假設，剩餘的k個頂點可用四種顏色著色。
● 當與v。相鄰的頂點的著色總數不超過3種時，v。著剩餘的第四色。
● 當與v。相鄰的頂點的著色總數為4時，有以下兩種情況：
(a). d( v。) =4，如圖1所示。
圖1 圖中1，2，3，4代表頂點所著的顏色。當上圖中著1，3的頂點之間不存在l[1,3]時，上圖中著3的頂點與著1的頂點不在g[1,3]的同一分支中，可將上圖中著3色的頂點所在分支中1與3兩色調換，於是v。可著3色。
當上圖中著1，3的頂點之間存在l[1,3]時，著2，4的頂點之間必不存在l[2,4]，同理可將上圖中著4色的頂點所在分支中4與2兩色調換，於是v。可著4色。
(b). d( v。) =5，必有一種色著了兩個頂點。
這兩個著同色的頂點要麼相鄰，要麼相隔乙個頂點（或兩個頂點）。不妨設這兩個同色頂點都著2色。當這個同色頂點相鄰時，如圖2所示。
證明方法同(a)。
圖2圖3
當這兩個同色頂點相隔乙個頂點（或兩個頂點）時如圖3所示。若上圖中著1，3的頂點之間不存在l[1,3]或著1，4的頂點之間不存在l[1,4]時，證明方法同(a)。上圖中著1，3的頂點之間存在l[1,3]且著1，4的頂點之間存在l[1,4]時，被l[1,3]和v。
組成的環包圍的著2色的頂點與著4色的頂點必不在g[2,4]的同一分支中，於是可將著2色的頂點所在的分支中2與4色調換，使2著4色，同樣被l[1,4]和v。組成的環包圍的著2色的頂點與著3色的頂點必不在g[2,3]的同一分支中，於是可將這個著2色的頂點所在的分支中2與3色調換，使2著3色，於是v。可著2色。
擴大環著色法
1.在圖中找到乙個內部沒有任何頂點的三角形，三個頂點著三種色。如果沒有補充乙個，再進行著色。於是構成乙個環。
2. 不斷將環外的頂點擴到環上，若要擴的頂點僅與環上的乙個頂點相連，則將其再與環上另乙個頂點相連。在已著色的區域的邊界上的頂點相連構成乙個環，每擴進乙個頂點，調整著色情況，始終保持環上的顏色數不多於3種。
此時擴進的頂點最多與三種顏色相連，可著第四種色，然後調整使所成的新環上的顏色數為3種。這樣就可4著色。具體方法如下：
a.若新擴入的頂點只與環上的兩種顏色相鄰，就將此頂點著環上的第三種色。此時新環上仍只存在3種顏色.不必調整。
b.若新擴入的頂點與環上的三種顏色相鄰，將此頂點著環上沒有的第四種色。此時環上可能已存在4種顏色。
不妨設原環上的三種顏色分別為1、2、3。新擴入的頂點著色4。與色4相鄰的三色中必然有一種色在環內，不妨設為色1。
如下左圖所示。
若不存在一條路l[4,1]或這條路中的末端著色l的頂點不在環上，則調換4，1。這樣環上就成了1、2、3三種顏色了。若存在一條路l[4,1]且這條路中的末端著色l的頂點在環上，
此時將這條路中的某個頂點v。（不包括這條路的兩端的頂點）的著色去掉，則在g[1,4]中，在新擴入的頂點所在的聯通分支將4與1色調換。於是環上的顏色就僅為1、2、3三種了，最後再給v。
著色。如果有多條這樣的l[4,1]，則都照此處理。
下面用歸納法證明v。可用4種顏色中的一種來著色。
當d(v。)<=3時，顯然可用4種顏色中剩餘的顏色來著色
假設當d(v。)=k時，v。可用4種顏色中的一種來著色。
那麼當d(v。)=k+1時，去掉與v。相連的一條邊(記去掉的這條邊的另乙個端點為v'，此時d(v。
)=k，由歸納假設可知，v。可用4種顏色中的一種來著色，不妨設v。著色4，其他與v。
相鄰的頂點除v'外分別著1、2、3中的一種。若v'著色為1、2、3中的一種，則著色完成；若v'著色為4，此時就需調整v'的著色。
若與v。相鄰的頂點之間存在與v。一起包圍色2的l[1,3]或包圍色1的l[2,3]，如上右圖所示，則在g[4,2]或g[4,1]中將v'所在的聯通分支中的著色4與2或4與1調換。
這樣著色完成。
若與v。相鄰的頂點之間不存在l[1,3]且不存在l[2,3]，則可將3換成或2，於是v。著色3。這樣著色完成。
於是v。可用4種顏色中的一種來著色。
四色猜想的證明
四色猜想的內容是 如果把地圖上有共同邊界的國家塗成不同顏色，那麼只需要4種顏色就足夠了。要證明四色猜想，首先需要定義一些新的概念 1 國家的表示法 點 由於該猜想的內容中不涉及與國家形狀有關的問題，而只涉及國與國之間的相鄰關係，因此任何乙個國家都用點來表示。2 相鄰與不相鄰 在敘述時，用符號 表示相...
四色猜想能夠成立的證明
作者 張爾光 科技視界 2018年第33期 摘要 本文依照 同一組的區域著同一色 的對等原理，將對四色猜想的四色區分的證明，置換為對 在相鄰區域不能搭配為同一組的原則下，能否做到將圖的區域合理搭配分為四組 的證明。筆者論證了 四色猜想的四色區分 的五種結果及其等式，創立了 設劃單元，合理搭配 的方法...
組合數學四色證明
四色問題的證明 如果你仔細留心一張世界地圖，你會發現用一種顏色對乙個國家著色，那麼一共只需要四種顏色就能保證每兩個相鄰的國家的顏色不同。這樣的著色效果能使每乙個國家都能清楚地顯示出來。但要證明這個結論確是乙個著名的世界難題，最終借助計算機才得以解決，最近人們才發現了乙個更簡單的證明。根據尤拉創立的 ...