关于四色猜想的逻辑推理

关于四色猜想的逻辑推理

【摘 要】 针对四色猜想，把图中任意一个区域周边与之紧邻区域的个数分

为奇数或偶数情况；再把一个区域及其周边与之紧邻区域组成的图形分为鳞状域

或围势域考虑，用数学归纳法证明了猜想成立。

【关键词】 四色猜想 紧邻区域 数学归纳法 奇数情况 围势域

Logical reasoning on the four-color conjecture

TANG Shijing1 TANG Zizhou2

（y school of Qiemo county xinjiang province，841900； school

of Qiemo county xinjiang province，841900）

【Abstract】 Against to the four-color conjecture， in any area in vicinities

thereto， the number of the immediate area can be divided into an odd or even ca；

then a region and its surrounding contrast to the immediate area consisting of graphics

into squamous domain or confining potential domain considered， the simple

mathematical induction to prove the conjecture is true.

【Key words】 The four-color conjecture The immediate area Mathematical

induction Odd ca Area surrounded trend domain

四色问题最初是由英国大学生古德里（Francis Guthrie）提出来的。1852年

他在搞地图着色时发现：“每幅地图可以用四种颜色着色，使得有共同边界的国

家都被着上不同的颜色”。

后来数学家们称之为四色猜想，归结为“在平面（或球面）上画地图，只要

有四种颜色即可保证相邻区域不用同一色”[1]。

肯普阐明了两个重要概念：“构形”和“可约”性。然而要证明很大的构形可约，

是相当复杂的。

1976年美国的阿佩尔（）和哈肯（）用“人与计算机合作”[2]

攻破了四色猜想。然而全球许多数学家都在不断探索严格的逻辑证明方法，他们

大致的方法是：从图论的角度考虑“对偶图”的顶点着色[1]；从拓扑学的角度考虑

区域的边界——简单曲线的线（边）着色[1]；“维定向-无定向闭曲面”[3]；“用有

限驾驭无穷”[4]；“邻点可区别全色数”[5]；或者考虑多面体的顶点边数等问题

[6]；……

拓扑学角度的四色问题可以转化为图论角度的“对偶图”着色问题。“对偶图”

是把地图中的每一个国家用其内部的一个点代表，作为一个顶点。若两个国家相

邻，就在两个顶点之间连一条线。它是原图着色问题的等价转化形式，顶点着色

和线（边）着色方法消除了原地图中与认识对象不相干的因素，并获得了一些重

要定理，这些定理当然适应于原图着色问题，否则就不是等价转化。

本文在相关定理的基础上数形结合，把原图中任意一个区域周边紧邻区域的

个数划分为奇数情况或偶数[7]情况；再把一个区域及其周边与之紧邻区域组成

的图形划分为鳞状或围势状考虑，从图中任意选定的一个域1开始，用数学归纳

法[8][9]，邻域递推、带带递归，证明了该猜想成立，而且由证明过程便可归纳

出涂色的方法步骤。

1 逻辑推理论证

1.1 鳞状域，围势域

鳞状域：相鱼鳞甲形状分布的区域。

三围域：对某些区域形成三面包围之势的域。

围势域：对某些区域有围括之势，却没有形成三面包围形状的域。

围势对域：与围势域接壤，二者对接后，对某些区域形成三面包围之势的域。

紧邻区域：互相接壤、边界线有一段相重合的区域。

度数：G中顶点V的度数是指G中与V关联的边的数目[1]

简单图：一个既没有圈也没有两条边连接同一对顶点的图[1]

对于任意给定的一幅未着色地图，首先讨论图中任意选定的一个域1及其周

边与之紧邻区域组成的图形，任一个域及其周边与之紧邻分为鳞状域或围势域。

区域组成的图形要么有围势域，要么没有围势域，二者必居其一。

当区域1的周边紧邻区域个数为n=1、2、3显然可用四色完成。红、黄、时，

绿、紫四种色依次记作a、bc、d。 、

假定区域1的周边紧邻区域个数为n=k时，可用四色完成。

则当区域1的周边紧邻区域个数为n=k+11的周边紧邻区时，只需把区域

域个数在k个的基础上再增加一个，即任意选其中一个域一分为二，新增加的这

个区域颜色隔域涂同色酌情填之。若与周边排不开就重新排列填涂颜色即可。这

是因为区域1涂的色若为a，2h+1要么为偶它的周边紧邻区域个数要么为奇数、

数2h。根据“设G是一个非奇回路的连通图，则G有一个2-边着色，其中两种

颜色在度数至少为2的每个顶点上都出现”[1]定理，可知为偶数时，鳞状域仅需

隔域涂同色——b、c交替排列h次即可涂遍区域1的周边紧邻区域。为奇数时

鳞状域仍需隔域涂同色——b、c交替排列h次，剩余的那个单域就用d。围势域

2与围势对域4，自成一对，虽内围括有区域而两域却相连、二者不同色，依次

为d、b，其内围括区域仍隔域涂同色——b、c交替排列，却不同于围势域的色

d，没有围势的域仍需隔域涂同色——b、c交替排列，三围域3一域两端各占一

位仍与隔域涂同色同理，仅在有围势域或剩余的那个单域处才需用d，对于既有

围势域又有剩余的那个单域的情况，由于在隔域涂同色时可以先把“单域”与围势

域分开，这两者不相邻可用同色d，也可把围势域作为“单域”涂色d。若围势域

的邻域还是围势域则两域不同色——一个填d，另一个填b或c，而隔域可涂同

色，其中色为d的围势域之内括域之色可为b、c交替排列，而紧邻着色为d围

势域的色为b围势域之内括域之色可为d、c交替排列，填c时同理。所以b、c、

d三色即可涂遍区域1的周边紧邻区域，而区域1用了一种不同于其紧邻域的色

a。由此可知对于域1及其周边与之紧邻区域组成的图形中、域的个数为任意一

个正整数时，都可以用四色完成，且保证相邻区域不用同一色（如图1 ）。

1.2 图中所有域

再证明全图可以用四色完成，保证相邻区域不用同一色。

因为对于域m=1及其周边与之紧邻区域组成的图形中、域的个数为任意一

个正整数时，都可以用四色完成，且保证相邻区域不用同一色。

假定区域m=k及其周边与之紧邻区域组成的图形中、域的个数为任意一个

正整数时，都可以用四色完成，且保证相邻区域不用同一色。

那么，区域m=k+1与区域m=k紧邻，且这两个域有公共的紧邻区域，公共

的紧邻区域的颜色及区域m=k的颜色作为基础色。基础色总共有两种或三种（例

如紫色围势域2与域1的情况），否则，若为四种色；那么m=k+1也是m=k的

紧邻区域，它既与m=k不同色也与公共的紧邻区域不同色，区域m=k及其周边

与之紧邻区域组成的图形中就有5种色，这与假定矛盾。区域m=k的色可能是a、

b、c、d中的任一种，有种可能，区域m=k的色先确定，区域m=k+1的色就有

种可能，公共的紧邻区域（相邻时）的颜色有种、或者m=k与m=k+1的两个“公

共的紧邻域”不相邻时（包括同色）有种情况，多个“公共的紧邻域”只是隔域涂

同色。根据“若G是完备图（一个简单图，它的每一对不同的顶点均有一条边相

连），则第一个点可在K种颜色中选一种，对于第二个顶点可在K-1种颜色中选

择一种，……，有（表示G的相异K-着色的数目），一般的有：若G是简单图，

则对G的任何边e，均成立”[1]定理，可知对于区域m=k+1的每一种可能来说基

础色有种、或者（m=k与m=k+1的两个“公共的紧邻域”不相邻时）有种可能。

如果m=k与m=k+1及其“公共的紧邻域”组成的图形不是简单图（即有三围域），

而m=k与m=k+1的两个“公共的紧邻域”要么相邻、要么不相邻，二者必居其一，

那么对于区域m=k+1的每一种可能来说基础色仍有种、或者有种可能。

区域m=k+1的周边紧邻区域个数要么为奇数2t+1、要么为偶数2t，若区域

m=k的色为a，区域m=k+1的色为b，公共的紧邻区域的颜色为c或d，或者两

色c，d。根据“设G是一个非奇回路的连通图，则G有一个2-边着色，其中两

种颜色在度数至少为2的每个顶点上都出现”[1]定理，可知为偶数时，鳞状域仅

需接着基础色隔域涂同色，c、d交替排列t次。再根据“设b=（E1，E2，…，Ek）

是G的一个最优k1-边着色，若存在G中的一个顶点u和颜色i及j，使i不出

现在u上，而j至少两次出现在u上，则G（EiEj）包含u的哪个Q分支是一条

奇回路”[1]定理，可知为奇数时鳞状域仍需隔域涂同色，c、d交替排列t次，这

是因为：t若小于2结果显然成立，若，由五色定理[1]成立知，区域m=k+1的周

边紧邻区域个数为奇数2t+1、再加其本身就多于5个，则恰符合该定理，而剩余

的那个单域显然与区域m=k不相邻（否则便是公共的紧邻区域），它填色a，相

邻域皆不同色。区域m=k+1的围势域与围势对域，自成一对，虽内围括有区域

而两域却相连、二者不同色。若围势域是区域m=k与区域m=k+1公共的紧邻区

域，则其色为基础色。若围势域不是区域m=k与区域m=k+1公共的紧邻区域，

区域m=k+1的围势域与围势对域色依次为a、d或a、c。色为a、d时其内围括

区域仍隔域涂同色——d、c交替排列，若其内围括区域为奇数2s+1个，则d、c

交替排列s次，最后c多排一次，恰好紧邻围势对域色为d，为偶数2s个时，则

d、c交替排列s次即可。色为a、c时同理。三围域一域两端各占一位仍与隔域

涂同色同理，仅在有围势域或剩余的那个单域处才需用a，对于既有围势域又有

剩余的那个单域的情况，由于在隔域涂同色时可以先把“单域”与围势域分开，这

两者不相邻可用同色a，也可把围势域作为“单域”涂色a。若围势域的邻域还是

围势域则两域不同色——一个填a，另一个填d或c，而隔域可涂同色，其中色

为a的围势域之内括域之色可为c、d交替排列，而紧邻着色为a围势域的色为d

围势域之内括域之色可为a、c交替排列，填c时同理。所以a、c、d三色即可

涂遍区域m=k+1的周边紧邻区域（例如紫色围势域2），而区域m=k+1用了一种

不同于其紧邻域的色b。上述所有种可能情况皆同理。

由此可知对于任意一个正整数m，区域m及其周边与之紧邻区域组成的图

形，域的个数为任意一个正整数时，都可以用四色完成，且保证相邻区域不用同

一色。

从图2中任意选定的一个域1开始，1周边紧邻区域围成的围域圈称为1域

围域带（如下图中2-6域围成），1围域带周边紧邻区域围成的围域圈称为2围域

带（如下图中7-18域围成），以此类推，这种“围域带”的边界线受各个域的面积

及形状影响可能有突出或凹陷。从1围域带上任选一域开始，所有邻域递推遍一

周后、接着2围域带与1围域带同法，带带递归下去。对于平面图用数学归纳法

同理推遍全图为止。在球面上从域1、1围域带开始围域带数不断增大，当出现

某一围域带上区域的面积或域的个数大到一定程度时，以后的同一围域带上区域

的面积或区域个数渐减，最后减为一个区域，所有区域围成了一个封闭的球面图，

证法同上理。

2 结语

由上述推理可知：任意选定的一个域及其周边与之紧邻区域组成的图形就能

成为数学归纳法递推的基础，且每次均以区域m=k+1与区域m=k公共的紧邻区

域的颜色及之前一个区域m=k的颜色作为基础色，任意两个域公共的紧邻区域

中相邻的区域皆不会同色。所以，“在平面（或球面）上画地图，只要有四种颜

色即可保证相邻区域不用同一色”。

参考文献：

[1]徐本顺，解恩泽.《数学猜想集》[M].湖南科学技术出版社，1999.2版，

152-179，240.

[2]AppelkI，lanarmapisfour-colourable[J].

.，1976，82：711-712.

[3]郭巍，郭应焕，郭振华，朱玉兰.《地图染色定理的证明》.前沿科学[J]，

2011年2期，53-58.

[4]王献芬，胡作玄.《四色的三代证明》.自然辩证法通讯[J].2010.4.

[5]孟献青.《联图的全染色及邻点可区别全染色》.硕士学位论文，2007.06.

[6]刘庆民，欧阳富，蔡汉忠《四色猜想的解析论证及其在地图绘制中的应

用》，浙江大学学报（理学版）[J].2011年4期，367-375.

[7]罗莫《四色猜想几何求证方法》.http：

///General/Blog/2011-1-4/676249.2011.01.04

[8]颜宪邦.四色定理论证的关键[J].航空计算技术，2004（3）：38-41.

[9]刘国瑞，刘国华.《四色猜想的证明》.中国科技论文在线，2006.01.23.

[10] Kauffman， L .H.： On the map theorem， Disc. Math. 229， 171-184

（2001）.

[11] Wilson， R. A.： Graph， Coloring and the Four-Color Theorem， Oxford

University Press， England， 2001.

[12] Charr， H.， Kocay， W.：A heuristic for 4-coloring a planar graph， J.

Combin. Math. .，46，97-112（2003）.