四色定理證明題目

為尊重“聘才職業(yè)圈”這個平臺上眾多給予幫助的專家，引用此文時，請注明“來自聘才職業(yè)圈”

為了打擊我根深蒂固的愚昧和狂妄，特懸賞：第一個發(fā)現(xiàn)證明0或證明2本質錯誤的人，可獲得小米手機一臺，略表謝意。證明1中，有一個錯誤，但可以彌補，不會影響結論。(我用的是WPS軟件，所以選擇小米。)

Hello, world!

I am becoming a machine.

本文所說的圖都是指平面圖。

方法0：

方法1：

數(shù)學歸納法：

最小4色圖是K4，含4個區(qū)域，4個點。

設圖含N(大于3)個點時，4色可染。若圖3色不可染，圖必然含至少2個區(qū)域，沒有一個固定區(qū)域必須4色染。(即允許有4色染的區(qū)域存在，但在圖上是可以流動的。類似于給圖4色染的時候，因為沒有精心的配置，會出現(xiàn)某個區(qū)域4色染的情況。)

增加1個點A,它必然第4色可染，圖4色可染。

若圖只有1個區(qū)域，則2色可染。所以，若圖3色不可染，圖必然含至少2個區(qū)域。

此時，含N+1個點的圖若存在一個固定區(qū)域必須4色染，則必然是A所在(或不在)的區(qū)域。

如果A所在的區(qū)域包含了所有點，則要么圖3色可染，要么A是N個點的環(huán)的中心點，無4色染的區(qū)域。

如果A所在的區(qū)域沒有包含所有點，因為我們可以任意指定誰是A,所以沒有一個固定區(qū)域必須4色染。

【另一種表述：因為必須4色染的圖必然含K3子圖，所以必然有1個3色染的區(qū)域。令3色染的區(qū)域含A(或者不含A)。而A卻是可以任意流動的,所以沒有一個固定區(qū)域必須4色染。】

根據(jù)歸納法可知，平面圖4色可染。

證畢。

方法2：

證明：

數(shù)學歸納法：

先觀察一下4色圖有什么特征：

最小的4色圖是K4，可以看作是C3加上一個中心點。

5個點的圖4色可染,當它必須4色染時,必有2個點，分別處于一個環(huán)的內外。

6個點的圖4色可染,當它必須4色染時,要么是C5加上一個中心點，要么是必有2個點，分別處于一個環(huán)的內外。

根據(jù)觀察，我們大膽假設：當圖含N個點時，4色可染，當它必須4色染時，要么含有子圖C(N-1)加上一個中心點，要么有2個點，分別處于一個環(huán)的內外。

我們先證明當圖含N+1個點時，圖4色可染：

去除N+1個點中任意一點A, 新圖含N個點。

如果新圖3色可染，則A第4色可染。圖4色可染。

如果新圖必須4色染，根據(jù)假設可知，要么新圖含有子圖C(N-1)加上一個中心點(此時，顯然A第4色可染)，要么有2個點(B和C)，分別處于一個環(huán)的內外。

不失一般性，我們可以假設A 和B處在同一個區(qū)域。

考察區(qū)域B所在點的染色情況：

若3色可染，則必有A第4色可染。

若必須4色染，根據(jù)假設可知，區(qū)域B要么有子圖C(N-X)加上一個中心點,

(X是某個自然數(shù)。此時，顯然A第4色可染)，要么含有兩個點E,F分別處于某個環(huán)的內外。

不失一般性，我們可以假設A 和E處在同一個區(qū)域......

因為圖是有限圖，所以A必然是第4色可染的。

所以N+1個點的圖4色可染。

命題得證。

待續(xù)，貼不下......為尊重“聘才職業(yè)圈”這個平臺上眾多給予幫助的專家，引用此文時，請注明“來自聘才職業(yè)圈”

為了打擊我根深蒂固的愚昧和狂妄，特懸賞：第一個發(fā)現(xiàn)證明0或證明2本質錯誤的人，可獲得小米手機一臺，略表謝意。證明1中，有一個錯誤，但可以彌補，不會影響結論。(我用的是WPS軟件，所以選擇小米。)

Hello, world!

I am becoming a machine.

本文所說的圖都是指平面圖。

方法0：