四色猜想的簡潔證明

田永成

(東北大學(xué)，遼寧 沈陽 110004)

0 引言

四色猜想是國際數(shù)學(xué)界疑存一百多年的數(shù)學(xué)難題，雖然在1976年，APPel和HaKen等利用電子計(jì)算機(jī)花了1260多機(jī)時(shí)證明了四色猜想，但是從數(shù)學(xué)家的價(jià)值觀看來，對四色猜想給出簡潔的理論證明還是十分必要的，這一問題的解決正說明數(shù)學(xué)難題用數(shù)學(xué)推理解決是完全可能的[2]。

本文只考慮簡單平面圖。若一個(gè)平面圖G的所有頂點(diǎn)均在它的同一個(gè)面的邊界上，則稱G是一個(gè)外平面圖，若對一個(gè)(外)平面圖G中任意兩個(gè)不鄰接的點(diǎn)u、v，G+uv均不是(外)平面圖，則稱G是一個(gè)極大(外)平面圖。未加說明的術(shù)語和記號參見參考文獻(xiàn)[1]。

1 四色猜想的證明

為了證明方便，先給出以下引理和定理：

引理1[1]若G是n(≥4)階極大平面圖，則3≤δ(G)≤5。

引理2[1]若G是n(≥4)階極大平面圖有e條邊，則e=3n-6。

引理3[3]每一個(gè)2連通平面圖可以嵌入平面使任何一個(gè)特定的面成為外部面。

定理1[1]以下三個(gè)命題是等價(jià)的：

(i)每個(gè)平面圖都是4頂點(diǎn)可著色的；

(ii)每個(gè)平面圖都是4面可著色的；

(iii)每個(gè)簡單2邊連通3正則平面圖都是3邊可著色的。

定理2 設(shè)G是n(≥6)階δ(G)=4的極大平面圖，則G存在4階極大外平面子圖是3點(diǎn)可著色的，由此子圖開始3點(diǎn)著色，可推出G是4點(diǎn)可著色的。

證對G的階數(shù)n(≥6)用數(shù)學(xué)歸納法證明：當(dāng)n=6(6是4正則極大平面圖的階數(shù))時(shí)可直接驗(yàn)證定理2成立。由引理2可知δ(G)=4不小于7階的極大平面圖G，至少有1個(gè)不小于5度的點(diǎn)，n=7時(shí)不存在有1個(gè)6度點(diǎn)的δ(G)=4的7階極大平面圖G，只存在2個(gè)5度點(diǎn)，它們的距離為2的7階極大平面圖，此圖是唯一的，如圖2.1G；若有1個(gè)3度點(diǎn)，3個(gè)5度點(diǎn)(其余的為4度點(diǎn))，該3度點(diǎn)與5度點(diǎn)均鄰接的7階極大平面圖G，此圖也是唯一的，如圖2.2G。

圖2.1 G 圖2.2 G

當(dāng)n=7時(shí)可直接驗(yàn)證定理2成立：在圖2.1G中取由u1，u2，u3，u4為頂點(diǎn)的G的4階極大外平面子圖開始進(jìn)行3點(diǎn)著色，其中d(u4)=4，進(jìn)而推出G是4點(diǎn)著色的，如圖2.1G；在圖2.2G中取由u1，u2，u3，u4為頂點(diǎn)的G的4階極大外平面子圖開始進(jìn)行3點(diǎn)著色，其中d(u4)=3，進(jìn)而推出G是4點(diǎn)可著色的，如圖2.2G；由圖2.1G、圖2.2G的4點(diǎn)著色過程可知：無論點(diǎn)u4的度數(shù)是否小于4都能推出G是4點(diǎn)可著色的。由引理3不防設(shè)G的最小度點(diǎn)u位于G的內(nèi)部面內(nèi)，以下同。

假設(shè)n-1(n≥8)時(shí)定理2成立，證明n時(shí)定理2也成立。

設(shè)G是n(n≥8)階δ(G)=4的極大平面圖，如圖2.3G；由前述分析知，在G中選擇1點(diǎn)u，它至少與G中1個(gè)不小于5度點(diǎn)如u2鄰接，d(u)=4，N(u)=﹛u1，u2，u3，u4﹜?V(G)，即d(u2)≥5。

從G中移去點(diǎn)u和與它關(guān)聯(lián)的邊，再連接邊u1u3，得n-1階極大平面圖G1，如圖2.4G1其中d(u4)≥4或d(u4)=3；若G1中d(u4)≥4，G1是滿足定理2假設(shè)條件的n-1階極大平面圖，故從G1的以u1，u2，u3，u4為頂點(diǎn)的4階極大外平面子圖開始3點(diǎn)著色，進(jìn)而推出G1是4點(diǎn)可著色的，如圖2.4G1；若G1中d(u4)=3，由前述分析，圖2.2G知：從G1的以u1，u2，u3，u4為頂點(diǎn)的4階極大外平面子圖開始3點(diǎn)著色，進(jìn)而推出G1是4點(diǎn)可著色的，如圖2.4G1。

將G1中的邊u1u3移去，在以u1u2u3u4u1為邊界的面內(nèi)添一點(diǎn)u，并連接邊u1u，u2u，u3u，u4u得滿足定理2條件的n階極大平面圖G，原G1中的點(diǎn)的著色不變，點(diǎn)u著4色，G是4點(diǎn)可著色的，以u，u2，u3，u4為頂點(diǎn)的G的4階極大外平面子圖是3點(diǎn)可著色的，如圖2.5G，故定理2成立，證畢。

圖2.3 G 圖2.4 G1 圖2.5 G

定理3 設(shè)G是n(≥12)階δ(G)=5的極大平面圖，則G存在5階極大外平面子圖是3點(diǎn)可著色的，由此子圖開始3點(diǎn)著色，可推出G是4點(diǎn)可著色的。

證對G的階數(shù)n(≥12)用數(shù)學(xué)歸納法證明：當(dāng)n=12(12是5正則極大平面圖的階數(shù))時(shí)可直接驗(yàn)證定理3成立。δ(G)=5的13階極大平面圖不存在；由引理2知，δ(G)=5不小于14階的極大平面圖G至少有1個(gè)不小于6度的點(diǎn)，n=14時(shí)不存在有1個(gè)7度點(diǎn)的δ(G)=5的14階極大平面圖，只存在2個(gè)6度點(diǎn)的距離為3的極大平面圖G，如圖3.1G，此圖是唯一的；若有1個(gè)4度點(diǎn)，3個(gè)6度點(diǎn)，該4度點(diǎn)與2個(gè)6度點(diǎn)鄰接與1個(gè)6度點(diǎn)的距離為2，此圖也是唯一的，如圖3.2G。當(dāng)n=14時(shí)，可直接驗(yàn)證定理3成立：在圖3.1G中取以u1，u2，u3，u4，u5為頂點(diǎn)的G的5階極大外平面子圖開始進(jìn)行3點(diǎn)著色，其中d(u5)=5，進(jìn)而推出G是4點(diǎn)可著色的，如圖3.1G；在圖3.2G中取以u1，u2，u3，u4，u5為頂點(diǎn)的5階極大外平面子圖開始3點(diǎn)著色，其中d(u5)=4，進(jìn)而推出G是4點(diǎn)可著色的，如圖3.2G；由圖3.1G、圖3.2G的4點(diǎn)著色過程可知，無論點(diǎn)u5的度數(shù)是否小于5都能推出G是4點(diǎn)可著色的。

假設(shè)n-1(n≥15)時(shí)定理3成立，證明n時(shí)定理3也成立。

設(shè)G是n(n≥15)階δ(G)=5的極大平面圖，如圖3.3G；由前述分析知，在G中選擇1點(diǎn)u，它至少與G中1個(gè)不小于6度點(diǎn)如u2鄰接，d(u)=5，N(u)=﹛u1，u2，u3，u4，u5﹜?V(G)，即d(u2)≥6。從G中移去點(diǎn)u和與它關(guān)聯(lián)的邊，再連接邊u1u3，u1u4，得n-1階極大平面圖G1，如圖3.4G1，其中d(u5)≥5或d(u5)=4；若在G1中d(u5)≥5，G1是滿足定理3假設(shè)條件的n-1階極大平面圖，如圖3.4G1，從G1的以u1，u2，u3，u4，u5為頂點(diǎn)的5階極大外平面子圖開始3點(diǎn)著色，進(jìn)而推出G1是4點(diǎn)可著色的，如圖3.4G1；若在G1中d(u5)=4，由前述分析，圖3.2G知：從G1的以u1，u2，u3，u4，u5為頂點(diǎn)的5階極大外平面子圖開始進(jìn)行3點(diǎn)著色，進(jìn)而推出G1是4點(diǎn)可著色的，如圖3.4G1。

圖3.1 G 圖3.2 G

將G1中的邊u1u3，u1u4移去，在以u1u2u3u4u5u1為邊界的面內(nèi)添一點(diǎn)u，并連接邊u1u，u2u，u3u，u4u，u5u得滿足定理3條件的n階極大平面圖G，原G1中點(diǎn)的著色不變，點(diǎn)u著4色，G是4點(diǎn)可著色的，以u，u2，u3，u4，u5為頂點(diǎn)的G的5階極大外平面子圖是3點(diǎn)可著色的，如圖3.5G，故定理3成立，證畢。

圖3.3 G 圖3.4 G1 圖3.5 G

定理4 設(shè)G是n(≥4)階極大平面圖，則G是4點(diǎn)可著色的。

證對G的階數(shù)n(≥4)用數(shù)學(xué)歸納法證明：當(dāng)n=4、5時(shí)可直接驗(yàn)證定理4成立。

假設(shè)n-1(n≥6)時(shí)定理4成立，證明n時(shí)定理4也成立。

設(shè)G是n(≥6)階極大平面圖，由引理1分以下3種情形證明：

δ(G)=3，G中存在1點(diǎn)u，d(u)=3，N(u)=﹛u1，u2，u3﹜?V(G)，如圖4.1G。從G中移去點(diǎn)u得n-1階極大平面圖G1，如圖4.2G1，由假設(shè)知G1是4點(diǎn)可著色的，u1，u2，u3分別著1、2、3色，如圖4.2G1；在G1中由u1u2u3u1所圍成的面內(nèi)添1點(diǎn)u，并連接邊u1u，u2u，u3u得n階極大平面圖G，原G1中點(diǎn)的著色不變，u著4色，則G是4點(diǎn)可著色的，如圖4.3G，此時(shí)定理4成立；

圖4.1 G 圖4.2 G1 圖4.3 G

由定理2、定理3知δ(G)=4，δ(G)=5時(shí)定理4也成立，證畢。

定理5(四色定理)設(shè)G是n(≥4)階簡單平面圖，則G是4面可著色的。

證由定理4及定理1的(i)，(ii)可證定理5成立，因而四色猜想是正確的。證畢。