四色定理證明題目

四色定理證明題目

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

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

Hello, world!

I am becoming a machine.

本文所說(shuō)的圖都是指平面圖。

方法0：

方法1：

數學(xué)歸納法：

最小4色圖是K4，含4個(gè)區域，4個(gè)點(diǎn)。

設圖含N(大于3)個(gè)點(diǎn)時(shí)，4色可染。若圖3色不可染，圖必然含至少2個(gè)區域，沒(méi)有一個(gè)固定區域必須4色染。(即允許有4色染的區域存在，但在圖上是可以流動(dòng)的。類(lèi)似于給圖4色染的時(shí)候，因為沒(méi)有精心的配置，會(huì )出現某個(gè)區域4色染的情況。)

增加1個(gè)點(diǎn)A,它必然第4色可染，圖4色可染。

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

此時(shí)，含N+1個(gè)點(diǎn)的圖若存在一個(gè)固定區域必須4色染，則必然是A所在(或不在)的區域。

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

如果A所在的區域沒(méi)有包含所有點(diǎn)，因為我們可以任意指定誰(shuí)是A,所以沒(méi)有一個(gè)固定區域必須4色染。

【另一種表述：因為必須4色染的圖必然含K3子圖，所以必然有1個(gè)3色染的區域。令3色染的區域含A(或者不含A)。而A卻是可以任意流動(dòng)的,所以沒(méi)有一個(gè)固定區域必須4色染�！�

根據歸納法可知，平面圖4色可染。

證畢。

方法2：

證明：

數學(xué)歸納法：

先觀(guān)察一下4色圖有什么特征：

最小的4色圖是K4，可以看作是C3加上一個(gè)中心點(diǎn)。

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

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

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

我們先證明當圖含N+1個(gè)點(diǎn)時(shí)，圖4色可染：

去除N+1個(gè)點(diǎn)中任意一點(diǎn)A, 新圖含N個(gè)點(diǎn)。

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

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

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

考察區域B所在點(diǎn)的染色情況：

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

若必須4色染，根據假設可知，區域B要么有子圖C(N-X)加上一個(gè)中心點(diǎn),

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

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

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

所以N+1個(gè)點(diǎn)的圖4色可染。

命題得證。

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

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

Hello, world!

I am becoming a machine.

本文所說(shuō)的圖都是指平面圖。

方法0：