田永成
(東北大學(xué),遼寧 沈陽 110004)
四色猜想是國際數(shù)學(xué)界疑存一百多年的數(shù)學(xué)難題,雖然在1976年,APPel和HaKen等利用電子計(jì)算機(jī)花了1260多機(jī)時(shí)證明了四色猜想,但是從數(shù)學(xué)家的價(jià)值觀看來,對(duì)四色猜想給出簡潔的理論證明還是十分必要的,這一問題的解決正說明數(shù)學(xué)難題用數(shù)學(xué)推理解決是完全可能的[2]。
本文只考慮簡單平面圖。若一個(gè)平面圖G的所有頂點(diǎn)均在它的同一個(gè)面的邊界上,則稱G是一個(gè)外平面圖,若對(duì)一個(gè)(外)平面圖G中任意兩個(gè)不鄰接的點(diǎn)u、v,G+uv均不是(外)平面圖,則稱G是一個(gè)極大(外)平面圖。未加說明的術(shù)語和記號(hào)參見參考文獻(xiàn)[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)可著色的。
證對(duì)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的以u(píng)1,u2,u3,u4為頂點(diǎn)的4階極大外平面子圖開始3點(diǎn)著色,進(jìn)而推出G1是4點(diǎn)可著色的,如圖2.4G1;若G1中d(u4)=3,由前述分析,圖2.2G知:從G1的以u(píng)1,u2,u3,u4為頂點(diǎn)的4階極大外平面子圖開始3點(diǎn)著色,進(jìn)而推出G1是4點(diǎn)可著色的,如圖2.4G1。
將G1中的邊u1u3移去,在以u(píng)1u2u3u4u1為邊界的面內(nèi)添一點(diǎn)u,并連接邊u1u,u2u,u3u,u4u得滿足定理2條件的n階極大平面圖G,原G1中的點(diǎn)的著色不變,點(diǎn)u著4色,G是4點(diǎn)可著色的,以u(píng),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)可著色的。
證對(duì)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中取以u(píng)1,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中取以u(píng)1,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的以u(píng)1,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的以u(píng)1,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移去,在以u(píng)1u2u3u4u5u1為邊界的面內(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(píng),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)可著色的。
證對(duì)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成立,因而四色猜想是正確的。證畢。