四色定理证明的新方法
梁增勇
摘要：本文用图论的方法证明了三角形结构连通图具有延伸和轮形两大的不可避免构形集。以及有它们组成的8个不可避免构形，它们的子图色数都≤4。通过分析这些构形的组合（图）的顶点颜色关系和运用顺序着色的方法完成图的正常4-着色。从而证明了三角形结构连通图（及平面连通图）的色数≤4。本文解决了切实可行的新方法对四色定理的书面证明，同时对四色定理的实际应用也具有一定的意义。
关键词：三角形结构连通图；不可避免构形集；延伸结构；轮形结构；顺序着色法
1 前言
四色猜想是世界数学界关注的问题，给出四色定理无需借助于计算机的证明仍然是一个未获解决的数学难题。我们已知四色定理可以通过证明平面连通图G'的色数≤4来实现。而平面连通图的色数不大于由它增加边而得到的三角形结构连通图G(triangulated graph) 的色数[1]。因此，只需证明任意三角形结构连通图的χ(G)≤4, 即可解决四色定理的证明难题。
2 三角形结构连通图
定义 1 如果一个简单图G它所有的内部的面都是C3,则称之为三角化图或三角形结构连通图[2]。
很明显，三角形结构连通图G可由平面连通图G '中内部所有长≥4 的圈增加边，使其所有内部面皆为C3而得。在图中增加边，只可能增加图的色数，所以χ(G’)≤χ(G) [2]。
图 1 平面连通图和三角形结构连通图
3 两大不可避免构形集
定义2 如果一个子图包括一个圈C n-1和一个中心顶点v，v和其它所有圈的顶点都邻接，则称之为轮形结构（轮图），简称轮形,用W n表示。不包含有轮形结构的三角形结构子图称为延伸结构，用E n表示。
图 2 延伸结构和轮形结构
在图2 中我们展示了延伸结构和轮形结构以及它们的同构子图，其中方形的子图是本文在分析中常用的形式。
定理1. 三角形结构连通图仅有延伸和轮形两种结构方式。
证. (1) 一个三角形有三条边，它与其它三角形邻接的情况只有三种：a)有一条公共边；
b)有两条公共边；c)有三条公共边。那么a和c属于延伸结构，b属于轮形结构。
图 2 一个三角形与其它三角形邻接的三种情况
(2)我们可以用逐个增加三角形来构造一个三角形结构子图（参见图3）。可用欧拉公式解释，在一个面中增加三个顶点和三条边可得一个三角形（C3）,它是三角形结构连通图的最基本的单位结构，由于它的形状和子图色数以及延伸结构的定义，我们将它归属于延伸结构。同时，用欧拉公式可以证明再增加三角形仅有两种情况：a) 为了增加一个三角形面需要增加一个顶点和两条边（E4,E7）；b)为了增加一个三角形面仅需要增加一条边。当仅为a的情况只可能产生延伸结构；当有b的情况会产生一个新的轮形结构（W4, W7）。（增加边数多于3 的情况不可能存在，因为新三角形仅有3 条边，且一条边必须是与旧三角形的公共边）（3）延伸结构和轮形结构之间的邻接组成的子图还是延伸结构或属于它们的并图，不会产生新的结构[3]。
图 3 增加一个三角形面与欧拉公式的关系
定理 2.延伸结构子图色数等于3。
证对n用归纳法。（1）当n=4时，χ(E4 )=3 。（2）假设χ(E n ) ≤4成立。那么增加顶点v n+1和两条边构成新的三角形, 顶点v n+1可使用与同在新三角形中的另两个顶点不同的颜色即可。所以E n+1的顶点所使用的的颜色种类集合还是在{1,2,3,4}范围之中，那么
χ(E n+1 ) ≤4也成立。
引理1轮图色数≤4 [4]。
以上说明，作为三角形结构连通图的不可避免构形集的两大类构形的色数都≤4 。下面我们研究以这两大类构形为子图所构造的三角形结构连通图是否色数也≤4 。
3 延伸结构和轮形结构的邻接
3.1 延伸结构与延伸结构:
a) 如果它们的公共部分是一条边，则它们的并图是一个新的延伸结构；
b) 如果它们的公共部分大于一条边（即等于或多于一个顶点和两条边），则产生新的轮形结构。
图 4 延伸结构与延伸结构的邻接
3.2 轮形结构和轮形结构邻接:
轮形和轮形邻接，基本不变。
图 5 轮形结构和轮形结构邻接
3.3 延伸结构和轮形结构邻接:
延伸结构和轮形结构邻，基本不变。
图 6 延伸结构和轮形结构邻接
4 图的简化和扩展
对于千变万化的复杂的三角形结构平面图我们必须找出对于它们具有代表性的简单可
行的结构图，我们称之为简化图，而这一过程称之为图的简化。反之我们可以由简化图反向恢复为任何的复杂的原图，我们称之为图的扩展。
定义4 .一个顶点和一条路径所有的顶点都邻接所成的子图称之为扇形结构，简称为扇形，用F n 表示。显然它属于延伸结构，(F n })=3。最小的扇形是F4, 其次是F5. 随着n 的增加，我们可以看到，以后的顶点的颜色仅仅是对F4或F5的复制而已。因此我们完全可以用F4或F5来作为简化图代表复杂的图。换句话说，它们已经包含所有扇形的信息，可以用在分析图中代表更大的扇形结构分析顶点颜色的关系。在需要的时候，也可以用复制的方法扩展成更大的扇形。
图11 扇形结构之间的顶点关系
轮形也是如此，是因为当轮形的中心顶点v0和两个公共端点v1,v2颜色确定之后，所有扩展的公共顶点v3, v4,..., v i顶点颜色也很容易确定。换句话说，所有扩展的公共顶点颜色仅与v0, v1, v2的颜色有关，因此扩展的公共顶点在简化图中可以省略。
图12 轮形
使用类似的方法，我们可以将延伸结构年和轮形结构的邻接方式归纳为三种模式并用简化图表示如下：
图13 轮形结构的邻接方式的三种模式及扇形
至此，我们已经找到构成任何三角形结构连通图的两大类不可避免构形集，和由它们组成的8个不可避免构形：E n , Y n , C3 , K3, F3 , Ⅰ型，Ⅱ型，Ⅲ型。任何复杂的三角形结构连通图都可由它们组成。
5 顶点颜色关系
在经典的使用计算机的四色定理证明中，只要把平面图的不可避免构形集找出和证明构
形的可约（可正常4-着色），就算完成四色定理的证明了。但我们将通过以下的证明步骤证明如果构形的不恰当安排（确定）也是不能完成正常4-着色的。换句话说，仅有前面的证明步骤，证明本身还是不充分的。
5.1 顶点颜色关系
定义5 .在K4,路径和两个轮形之间的顶点颜色，仅受与它们周围邻接的顶点的颜色限制（发生关系），并称为色自由顶点（见下图红色顶点）。因此，必要时也可以在简化图中予以省略，或者在顺序配色程序的最后步骤才确定它们的颜色。
图14 各种色自由顶点案例
定义 6 . 在给定的色数范围内，子图的顶点颜色会呈现固定顺序的现象（性质）称之为有序图，反之称为无序图。例如：2色图中的路径和偶圈，给定3色的延伸结构子图。
图15 各种有序子图
定理3给定3色的延伸结构子图是有序图。
证我们用数学归纳法：（1）显然，当n=4, 任意两个三角形组成的延伸结构子图$E_{4}$ 是有序图。
(2) 假设当n=k, 三角形组成的延伸结构子图E k 是有序图。那么，添加第k+1个顶点v k+1和两条边构成新的三角形（面），顶点v k+1须使用与同一个三角形的另两个顶点不同的颜色，即与它对边所对的另一个邻接三角形的顶点同色，这就是它所保持的颜色顺序。所以E k+1也是有序图。
定义7 . 如果在一个有序图的两个相同颜色的顶点还邻接一条公共边，这是正常k-着色不允许的,称之为颜色冲突。
例如，下图中v1和v3k+1发生了颜色冲突。由于v1和v3k+1构成一个多边形，因为三角形结构图内部无多边形的面，显然它是轮形的边。解决颜色冲突的办法是改变轮形中心顶点的位置，见图13：
图16 颜色冲突的产生原因及消除方法
定理4 . 改变轮形的中心顶点的位置可以消除顶点颜色冲突。
证假设延伸结构的顶点v1和v3k+1存在边v1和v3k+1并发生了颜色冲突。由于v1和v3k+1及它们的边构成一个多边形（边数大于3），而三角形结构图内部无多边形的面，显然它是轮形的边。解决颜色冲突的办法就是改变轮形中心顶点的位置，将所有轮形中非端点的其中之一种颜色的顶点，与轮形中心顶点对换颜色。（即改变轮形的中心顶点的位置），那么，原来的有序图的固有颜色顺序将被破坏，消除颜色冲突（见图16）。
例如：
（1）在下图中左边的分析图显示按照一般情况配色，有一对顶点颜色冲突是不可解决的。
（2）在下图中右边的分析图显示按照特殊情况处理，经过改变轮形结构的中心顶点位置，改变了上面的延伸结构顶点颜色的顺序，颜色冲突消除，该块可实现正常4- 着色。
图17 颜色冲突及消除的案例
5顺序配色法
在上节中我们已经了解在三角形结构连通图G中延伸结构是被轮形结构分隔的，我们可以将图G做好一个初步的结构位置规划（或称之为{预分配}）。在规划构形位置时形成轮形包围延伸结构的布局，使之出现更多小的延伸结构。然后逐个对延伸结构使用颜色关系分析图进行分块分析和配色，直至完成落实全部图的顶点的4-正常着色，这一方法称之为顺序配色法。下面我们将通过顺序配色法完成以后的证明部分。
18顺序配色法的基本步骤
4.1 顺序配色法的基本步骤:
顺序配色法的基本步骤是：
(1) 首先做好一个初步的轮形结构位置规划（或称之为预分配）见图7中第2个图，用粗线表明轮形的边.。
(2) 用颜色关系分析图对一组相邻延伸结构和轮形结构组合的块进行配色。见图7中第
3个图，上好颜色的顶点是一个块。两个延伸结构（E10 ，E13）中间隔着三个轮形（W4，W4，W8, W7, W7），它们组成了一个颜色关系分析图（见图8）。
（3）如此按照延伸结构的顺序一个接一个地完成正常4-着色。
(4) 最后完成整个图的正常4-着色。
图19 一个块和它的颜色关系分析图
4.2 颜色关系分析图
4.2.1 颜色关系分析图
在图8中，用方形结构图表示两个延伸结构和中间相邻的轮形结构，较方便分析各顶点的颜色关系，称之为颜色关系分析图。它包含两个子图，左边是部分未上好色的，右边是全上好色的（见图9）。
左图中下部E16是前面已经着好色的延伸结构；上面的E14是本次需要配色的延伸结构，中间隔着4个轮形（注：为了分清轮形与延伸结构，将所有轮图的与中心顶点邻接的边用浅色线表示或者隐藏）。
图20 一般情况下的颜色关系分析图
右图是一般情况下E14得到正常4-着色的结果。轮形中心顶点用白色。由于延伸结构的色数是3，延伸结构的顶点用另外三色。在一般情况下无颜色冲突。
由于E16的顶点颜色保持不变，所以本块顶点的颜色和其它已着色的块的顶点保持正常的4-着色关系。
4.2.2 严格的交接边界
在进行顺序配色过程中每两个块的交接边界的顶点（见下图中红色线条中的顶点）颜色是不能改变的，这就保证了当前块B i和已完成着色的子图G i-1顶点之间的颜色既有含接又无颜色冲突的要求。因此
图21 两个块的交接边界的顶点
令G i-1为第i-1步已着色区域的子图，B i为本次分析图所包含的块，那么
C(G i) = C(G i-1) ∪C(B i) (3)
由于χ(G i-1)≤4 , χ(B i)≤4 , C(G i)也≤4 。
此时，我们只要分析在颜色关系分析图中的块的顶点是否可以正常4-着色，就可以证明顺序着色法是否可以将图G正常4-着色。换句话说，当在颜色关系分析图中的顶点都可以正常4-着色，那么，图G的色数就≤4。
4.2.2 对颜色关系分析图的分析
4.2.2.1 复杂的颜色关系分析图
如果我们的预规划不是很周到，所得到的延伸结构可能是很复杂很大的一个子图。例如图，它包含了所有三角形结构连通图的不可避免构形。
图10
将颜色关系分析图再拆分，可得到小的基本不可避免构形，我们可以从左到右的将每个构形进行正常4-着色。那么一个颜色关系分析图的块是否能正常着色，就取决于每一个构形的组合是否可以正常4-着色。使用组合的方法，我们可以得到6
图22 Ⅰ型构形的扩展（左方向）
4.2.2.1 Ⅰ型构形组合分析
首先，我们讨论Ⅰ型构形组合的正常着色。图（1）是没有着色的，在颜色关系分析图中v1、v2、v3是在前面步骤已经着色的顶点，而v4、v5 是将要着色的新顶点。而v1、v2、v3可能出现的有（2）、（3）和（4）三种着色情况。而（2）、（3）种情况是容易处理的，正常着色见图。但（3）种情况出现不能解决的颜色冲突。
图23 Ⅰ型构形的扩展（左方向）
此时，我们必须调整（3）的构形组合附近的顶点颜色，见图。它周围的（主要是左边邻接的构形顶点）可能出现的情况如（1）、（2）。
1）左边邻接的构形是两个轮形结构：
图24 Ⅰ型构形的扩展（左方向）
图26 Ⅰ型构形的扩展（轮形方向）
至此我们已经介绍对Ⅰ型构形的正常4-着色的证明，对于其它Ⅱ型和Ⅲ型构形的组合也可以用相似的方法证明他们可以正常4-着色。但我们不打算继续这样烦琐的证明。
4.2.2.1 颜色关系分析图优化
对于其它形式的构形组合，我们完全可以在颜色关系分析图中进行优化，将所有的构形组合转化为Ⅰ型组合。
图27 Ⅰ型构形的扩展（左方向）
5.5 其它特殊的情况
此时，还有一些特殊的情况如下：
(1)轮形结构之间夹有多条放射结构的边。
（2）不规则轮形结构。
（3）多重轮形结构。
它们的处理方法同样可按照上面的处理方法，重新安排轮形的位置，使所有延伸结构和轮形结构的组合成为Ⅰ型组合的关系。
图28 特殊情况下的颜色关系分析图处理
现在我们已经将复杂的三角形结构图可能存在的构形组合枚举完毕。以上证明了，不管三角形结构图G的结构如何复杂，都可以通过顺序着色法将图G完成正常4-着色。5.4 关于K4的处理
因为不管K4的三个外圈的顶点颜色如何，中心顶点总可以使用与它们不同的第四种颜色，为了简化分析程序，我们在顺序配色过程的开始将K4看作C3处理，如同所有自由顶点的处理方法一样，直至程序的最后一步，才确定所有K4的中心顶点的颜色。
图29 K4 的处理案例
5.6 一个完整的顺序配色法的实施案例
（1）首先将K4看作C3,预规划轮形结构的位置。在图中为区分轮形，将它们的外圈边用粗线条表示。(为区分K4 ，将它的中心顶点画小)。
（2）选择一个延伸结构着色，作为第一个块B1。
（3）以邻接它的第二个延伸结构决定划分第二个块B2 , 并进行分析配色。
（4）如此类推完成所有大的延伸结构（也包括了轮形结构）的顶点配色。
（5）最后对所有小的自由顶点（包括K4）进行配色。
图30 一个完整的顺序配色法的实施案例
6 命题证明
定理5（四色定理）.任何平面连通图是4-可着色的。
证. (1) 设G‘是一个平面连通图, G是由G ‘增加边而得到的三角形结构连通图~. 那么由（1）可知χ(G ')≤χ(G) .
(2) 运用顺序配色法，将G划分为延伸结构和轮形结构的组合，同时按顺序将这些结构组成不同的块，并逐个按顺序完成块的颜色配色，由上面的分析可知图G是这些子图（块）的并图，且每个子图的色数≤4 。使用顺序配色法，同时每个块之间没有颜色冲突。那么令B i表示本块子图，E1、E2、...、E j和W1、W2、...、W k分别为它所含的延伸结构和轮形结构。则
C(B i) = C(E1) ∪C(E2) ... ∪C(E j) ∪C(W1)∪... ∪C(W1). （5）
由于每个延伸结构和轮形结构的色数≤4，同时每个结构之间没有颜色冲突。所以
χ(B i )≤4 。
（3）另外，我们用S表示所有自由顶点的集合，C(S)表示它们颜色种类的集合，由自由顶点的定义可知，它们与周遍的顶点没有颜色冲突，可以使用4种颜色范围的色，因此，
C(S)={1,2,3,4} 。
那么
C(G)=C(B1)∪C(B2)∪... ∪C(B i)∪C(S) (6)
因为根据（5）可得出所有C(B1) 、C(B2) 、... 、C(B i) 都∈{1,2,3,4} ，同时C(S)∈{1,2,3,4}所以C(G)∈{ 1,2,3,4 } ,那么
χ(G) ≤4 。
最后，由（1）可得χ(G’ ) ≤χ(G )≤4 。即任何平面连通图G'的色数不大于4 。
证毕。
9 结论
通过以上分析证明，任何平面连通图G'都可以通过增加边得到它对应的三角形结构连通图G，它们的色数χ(G’ ) ≤χ(G )≤4, 这就完成了四色定理的证明。另外，应该看到，本文同时解决了如何对任何一个平面连通图实施正常4-着色。这对四色定理的证明和应用都有着实际的意义。
参考文献
[1]R.Balakrishnan , K.Ranganathan,, A Textbook of Graph Theory[M]科学出版社，:北京：2011（187-188）
[2] 王树禾，图论[M] 北京：科学出版社，2004：（90）
[3] 屈婉玲，耿素云，张立昂，离散数学[M]高等教育出版社，北京：2008：（324-325）
Pure Mathematics 理论数学, 2019, 9(8), 949-960 Published Online October 2019 in Hans. https://www.doczj.com/doc/8b194411.html,/journal/pm https://https://www.doczj.com/doc/8b194411.html,/10.12677/pm.2019.98121 Tait’s Conjecture Continue —The Proof of the Four-Color Theorem Wenzhen Han Jincheng Energy Co. Ltd., Jincheng Shanxi Received: Sep. 30th, 2019; accepted: Oct. 22nd, 2019; published: Oct. 29th, 2019 Abstract The four-color theorem also known as the four-color conjecture or the four-color problem is one of the world’s three largest mathematical conjecture. Although it has been proved on computer, which owes to its powerful computing ability, after all, it isn’t strictly reasoned mathematically. Lots of math enthusiasts devote themselves to studying the problem around the globe. In this pa-per, the new concepts of two-color dyeable continuous line are put forward. A new method is used to prove that the 3-coloring of 3-regular planar graph lines is equivalent to the 4-coloring of maximal graph points. It is also proved that the 3-coloring of 3-regular planar graph lines is in-evitably possible. Thus, a universal four-color coloring method for vertices of any maximal graph is given. Keywords Four Colors Enough, Two-Color Dyeable Continuous Line, 3-Regular Plane, Maximum Graph, Even Ring Elimination Method 泰特猜想的延续 ——四色定理的书面证明 韩文镇 晋城能源有限责任公司，山西晋城 收稿日期：2019年9月30日；录用日期：2019年10月22日；发布日期：2019年10月29日 摘要 四色定理，又称四色猜想、四色问题，是世界三大数学猜想之一。计算机证明虽然做了百亿次判断，终
四色猜想的证明 吴道凌 （广东省广州市，510620） 摘要：四色猜想至今未得到书面证明。根据其定义的国家概念和着 色要求，揭示了无限平面或球面上任意国家及其邻国的构成和着色规 律，从而给四色猜想一个书面证明。 关键词：四色；猜想；证明；国家；着色 中图分类号：O157.5 文献标识码：A 1852年，英国学者弗南西斯·格思里(Francis Guthrie)提出，“每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色”，这就是后来数学上著名的四色猜想。对此猜想，一百多年来曾有无数学者予以研究，但人工验证均无功而返。1976年，美国数学家阿佩尔(Kenneth Appel)和哈肯(Wolfgang Haken)利用电子计算机，作了大量判断，对四色猜想进行了机器证明，但这一证明不能由人工直接验证，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任，因此并不被人们普遍接受。 本文拟根据四色猜想定义的国家概念和着色要求，研究无限平面或球面上国家的构成及其着色规律，寻找对四色猜想的书面证明。 1 四色猜想相关定义及表述方法 四色猜想所指的国家，是指连续的区域，可为单连通区域，也可为多连通区域，不连续的区域不属一个国家。共同边界指相邻国家有无数个共同点，四个或四个以上的国家不交于一点，或者说，这种交点不认为是共同边界， 只有这种交点的国家不需区分着色。 四色猜想并未限制地图范围，地图可定义在球面或无限平面 上。在球面上的任何国家，将存在一个外边界，由一条简单闭曲线 构成，在无限平面上的国家，一般也由一条简单闭曲线构成外边界， 个别国家也许在某些区间不存在边界（即区域无限延伸），其外边 界将由若干段曲线构成，对于这种情况，我们可在其无限远处虚拟 若干个国家若干段边界，与实在的若干段边界构成一条简单闭曲线 边界，这种做法实际上提高了这些国家的着色要求，因此不影响本 命题的论证。如为单连通区域，国家里边将不存在内边界，如为多 连通区域，国家里边将存在若干由简单闭曲线构成的内边界。因此，为使命题具有普遍性，把国家定义为具有一个外边界和若干内边界的区域，每 一边界均为该国与若干邻国的共同边界构成的简单闭曲线，如图1 示。下面把构成一条这种共同边界闭曲线的若干邻国称为一个邻国 圈。 用小圆圈表示邻国，两国相邻时，用线条连接两个小圆圈， 一个邻国在共同边界多处出现时，各处分别用小圆圈表示，并用线 条连接各处表示连通。把一个国家表示为由其若干邻国圈构成的闭 合圈围闭的区域，如图2示。其中，外闭合圈之外，一些邻国可能 跨越闭合圈上的一个或多个邻国与其它一个或多个邻国相邻，一些 邻国也可能多处出现在闭合圈上，这些情况将使闭合圈外存在若干
简洁破解四色猜想 ——“1+3”证明与“3+1”充要条件模型证明—— 李传学 四色猜想与费马猜想、哥德巴赫猜想，是数学界三大难题。本文利用“1+3”、“3+1”链锁思维方式，并结合计算机逻辑判断方式，给予地球四色猜想的有、且只有数学方法与应用方法的两种证明。并在实践中，使链锁着色，直至组成四色猜想的（△）网状平面整（总）体地图。 一、四色猜想简洁证明的提出。 随着计算机运算速度的加快、人机对话智能的出现，极大加快了对四色猜想研究、证明的步伐。1976年6月，美国哈肯与阿佩尔编制程序，利用1200个小时，分别在两台计算机上，作了100亿次判断，终于完成了四色猜想的证明。到目前为止，仍是世界上唯一被认可的证明方法。但是，由于计算机证明方法过程深长，不符合人的逻辑思维判断过程，缺乏简洁性，无法令人信服。 二、“四色”是地球“四方八位”的客观存在。 “四方八位”是个动态概念，存在于“天、地、人合一”的地球万物运动的整个过程中。同样，数学界三大难题之一的四色猜想，也离不开这一客观规律。 地球，蕴育了万物。天圆地方、“四方八位”、四面八方、东西南北、五湖四海是人类认识地球的思维方式。远在史前人类整体文明时期，就有文物记载了地球上有关“四方八位”的许多概念。如半坡人鱼盆、人网盆、含山玉版、澄湖陶罐、八角星陶豆、良渚陶璧、古埃及金字塔，以及其他图形、符号记载的伏羲八卦图、彝族八卦图、河图、洛书、五行属性，也都应用了“四方八位”概念。 四色绚丽的地球生生不息，是“天人合一”的赋予。地球的天圆地（四）方是阴阳学说的核心和精髓，又是阴阳学说的具体体现，具有朴素的辩证法色彩，是古代人类认识世界的思维方式。 阴阳五行中的五色、四方位：即，木有青、东，金有白、西，火有红、南，水有黑、北，土有黄、中，以及罗盘定位、经纬仪、四季、纳米四大光波（红、蓝、绿、黄）、四色光谱仪都与地球上的“四方八位”寓意紧密相关。当然，“四色猜想”也不例外，也只能有、且只有在地球图上的客观存在。 三、四色猜想的数学语言定义。 任何一张平面地图，只要用四种不同颜色就能使具有共同边界的国家，着上不同颜色，称之为四色猜想。 四色猜想的数学语言定义：将平面任意地细分为不相重叠的区域，每一区域总可以用1、2、3、4这四个数字之一来进行标记，且不会使相邻的两个区域得到相同的数字。这里的相邻区域，是指有一整段（非点）边界是公共的边界（注：据网络“科普中国”）。 四、四色猜想的数学证明。
证明四色猜想 本文用递推的方法，分别用点和线代替平面图形及平面图形相交，则三个平面图形两两相交时，构成一个三角形的封闭空间。通过讨论第四个点与此三角形的关系，简明地证明了四色猜想。 四色猜想最先是由一位叫古德里的英国大学生提出来的。高速数字计算机的发明，促使更多数学家对“四色问题”的研究。就在1976年6月，哈肯和与阿佩尔合在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍有不少数学家和数学爱好者在寻找更简洁的证明方法。 证明 将平面图形抽象极限成成点或线，当然在这一点或线的基础上可以任意发出一些线（这些射线可以任意扩展为面）。这些射线都属于这个点。 首先，A，B两个面相交看成点A发出的射线和点B发出的射线相遇于点Pab，如图1。第三点C要和A，B两两相交，则构成一个三角形ABC的封闭空间，如图2。 这时点D要和A、B、C两两相交则有两种情况： （1）D在ABC之内和ABC相交 当D和和A、B、C中任意两者相交都将构成新封闭三角形。第五点E继续相交时就和D与A、B、C相交的情况一样。 假设D和A，B，C分别相交于Pad，Pbd和Pcd。Pbd在P到B点间，Pad 在Pac到A点间，Pcd在Pac到C点间。这样即使A，B，C内部还有剩余空间也被分成了3部分如图3。尽管这三个图形不一定都是三角形但都是封闭的，都可以简化成三角形。所以无论第五点E在哪部分都是点与三角形关系。（见图3） （2）D在ABC之外和ABC相交 D可以完全将ABC包围或者将ABC一部分包围。但无论怎样ABC三者至少有一者完全在D的图形内。 若D将ABC一部分包围。那么ABC至少有一点完全被D包围。如图5 若E在D外就不能和A、B同时相交。
四色定理的简单证明 虽然现在已经有不少人用不同方法证明出了四色定理，但我认为四色定理的证明还是有点复杂,所以给出以下证明。（注：图形与图形的位置关系可分为相离、包含、内向接、内向切、外向接、外向切，在此文中由于题意关系不妨重新分为以下关系：1 把包含、内向接、内向切，统一划分为包含关系。2 把外向接单独划分为相接关系。3把相离、外相切统一划分为相离关系。） 此证明过程中把图的组合形式按照其位置关系而抽离出了以下四种基本有效模式： 1 若要存在只需用一种颜色便能彼此区分开来的地图，则该图中所有图形必定满足彼此相离。如下图： 图（1） 分析：这是最简单的一种图形关系模式暂且称为模式a。 2 若要存在只需用两种颜色便能彼此区分开来的地图，则该图中的所有图形必定满足最多只存在两个图形的两两相交的图形。各种有效图形关系如下图：
图（2） 分析：两个图形的两两相交的所有图形关系均可变形而得出等价的以上两种图形关系模式之一。由于图（1）存在包含关系，被包含的图形是对外部无影响的，所以图（1）仍属于模式a。所以两个图形的两两相交只有图（2）的相交关系模式的图形有效的，我们暂且称之为模式b。 3 若要存在只需用三种颜色便能彼此区分开来的地图，则给图中所有图形必定满足最多只存在三个图形的两两相交图形。各种有效图形关系如下图： 图（3） 分析：三个图形的两两相交的所有图形关系均可变形而得出等价的以上两种图形关系模式之一。由于图（2）属于存在包含关系，同理整体回归于模式a。所以三个图形的两两相交只有图（1）的相接关系模式的图形是有效图形模式，我们暂且称之为模式c。 4 若要存在只需用四种颜色便能彼此区分开来的地图，则给图中所有图形必定满足最多只存在四个图形的两两相交图形。各种有效图形关系如下图： 图（4）
四色定理的证明 一、四色定理的介绍 地图四色定理最先是由一位叫古德里的英国大学生提出来的。 四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2， 3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。1976年美国数 学家阿佩尔与哈肯宣告借助电子计算机获得了四色定理的证明，又为用计算机证明数学定理开拓了前景。 二、四色定理的证明 通过四色定理的介绍，我们可以知道如果两个图形相邻，则需要用不同的颜色将它们区分。反之，若两个图形不相邻则可以用一种颜色。由此得出，如果一张地图不能用四种颜色将它们分开，则必然存在五个两两相邻的图形。所以，只需证明是否存在五个两两相邻的图形即可。 1.把一个图形X 分成2个小图形的情况共有两种。分别如下： 图 2 说明：a.图形X 的选取是任意的(在这里举的是一个圆）。 b.将图1的分法叫线切法，点M,N 为交点，其特点是两个图形都只共用自己的一部分 边界。将图2的分法叫内取法，其特点是其中一个图形所有边界与另一个图形共用。内取法的性质是里面的图形B 只能与图形A 相邻，称图形B 为内取图形。 2.将一个图形X 分成3个小图形的情况共有6种，方法是先把一个图形分成两个，再把其中 一个分成两个。对图1因其分成的两个图形是等价的所以共有2种（如图3和图4），对图2的继续分共有4种（如图5到图8）。分别如下： 图5 图6 图8 从中我们可以看出，只有图3、图5和图7是满足两两相邻的。 3.将一个图形X 分成4个小图形两两相邻的情况。方法是先把图形X 分成2个小图形A 和 B ，再把B 分成3个小图形B1、B2和B3。又因为分成3个图形满足两两相邻的只有图3、图5和图7三种分法，图5和图7有内取图形无法与图形A 相邻，故要想满足4个图形两两相邻只能采取图3这种分法。 P
四色定理证明的新方法 梁增勇 摘要：本文用图论的方法证明了三角形结构连通图具有延伸和轮形两大的不可避免构形集。以及有它们组成的8个不可避免构形，它们的子图色数都≤4。通过分析这些构形的组合（图）的顶点颜色关系和运用顺序着色的方法完成图的正常4-着色。从而证明了三角形结构连通图（及平面连通图）的色数≤4。本文解决了切实可行的新方法对四色定理的书面证明，同时对四色定理的实际应用也具有一定的意义。 关键词：三角形结构连通图；不可避免构形集；延伸结构；轮形结构；顺序着色法 1 前言 四色猜想是世界数学界关注的问题，给出四色定理无需借助于计算机的证明仍然是一个未获解决的数学难题。我们已知四色定理可以通过证明平面连通图G'的色数≤4来实现。而平面连通图的色数不大于由它增加边而得到的三角形结构连通图G(triangulated graph) 的色数[1]。因此，只需证明任意三角形结构连通图的χ(G)≤4, 即可解决四色定理的证明难题。 2 三角形结构连通图 定义 1 如果一个简单图G它所有的内部的面都是C3,则称之为三角化图或三角形结构连通图[2]。 很明显，三角形结构连通图G可由平面连通图G '中内部所有长≥4 的圈增加边，使其所有内部面皆为C3而得。在图中增加边，只可能增加图的色数，所以χ(G’)≤χ(G) [2]。 图 1 平面连通图和三角形结构连通图 3 两大不可避免构形集 定义2 如果一个子图包括一个圈C n-1和一个中心顶点v，v和其它所有圈的顶点都邻接，则称之为轮形结构（轮图），简称轮形,用W n表示。不包含有轮形结构的三角形结构子图称为延伸结构，用E n表示。
图 2 延伸结构和轮形结构 在图2 中我们展示了延伸结构和轮形结构以及它们的同构子图，其中方形的子图是本文在分析中常用的形式。 定理1. 三角形结构连通图仅有延伸和轮形两种结构方式。 证. (1) 一个三角形有三条边，它与其它三角形邻接的情况只有三种：a)有一条公共边； b)有两条公共边；c)有三条公共边。那么a和c属于延伸结构，b属于轮形结构。 图 2 一个三角形与其它三角形邻接的三种情况 (2)我们可以用逐个增加三角形来构造一个三角形结构子图（参见图3）。可用欧拉公式解释，在一个面中增加三个顶点和三条边可得一个三角形（C3）,它是三角形结构连通图的最基本的单位结构，由于它的形状和子图色数以及延伸结构的定义，我们将它归属于延伸结构。同时，用欧拉公式可以证明再增加三角形仅有两种情况：a) 为了增加一个三角形面需要增加一个顶点和两条边（E4,E7）；b)为了增加一个三角形面仅需要增加一条边。当仅为a的情况只可能产生延伸结构；当有b的情况会产生一个新的轮形结构（W4, W7）。（增加边数多于3 的情况不可能存在，因为新三角形仅有3 条边，且一条边必须是与旧三角形的公共边）（3）延伸结构和轮形结构之间的邻接组成的子图还是延伸结构或属于它们的并图，不会产生新的结构[3]。 图 3 增加一个三角形面与欧拉公式的关系 定理 2.延伸结构子图色数等于3。
一、问题描述： 问题1：平面上任意不重叠的区域，仅采用4种不同的颜色即可对区域进行填充，而使得相邻区域的颜色不同。 上述问题可转换为： 问题2：平面上只存在至多4个点能够互相连接，而连接的线不交叉。 二、问题1和问题2的等价性： 两个区域相邻具有特性：任意分别属于两区域的两点之间都存在一条线连接，这条线仅属于这两个区域。 对于4个区域，任意4个点分别属于不同的区域，4个点互相不交叉连接即代表区域之间是相邻的，因此需要4种颜色填充。而如果存在第5个点使得这个点与其它点能连接而不与其它连接线交叉，则意味着这5个点所属的5个区域相邻，则需要5种颜色进行填充。如果交叉即意味着连接线代表的区域被截断变成不相邻。 因此只需要证明平面上不可能存在第5个点符合下述条件： 条件：第5点与其它4个点连接而不与其它连接线交叉。 三、问题2的证明： 3.1、显然的，平面上任意3个不同点能够两两相连，形成一个封闭的区域，如下图所示。3个点连接线将平面划分成了2个部分：区域ΩABC与区域ΩABC~；ΩABC构成一个封闭的区域。 B 3.2、第4个点D的位置有两个选择： 3.2.1、选择1，第4个点D区域内：
B 此时区域ΩABC被分为3个区域：区域ΩABD、ΩACD、ΩBCD。且这3个区域均是封闭的。第五个点E，可选择的位置有两种情况： 第一种情况：点E在区域ΩABC~ 在这种情况下，由于E在封闭区域ΩABC外部，而D点在封闭区域内部，因此，E点与D 点相连必定要穿越区域ΩABC的边界，即E与D的连接必与其它连接线交叉。如下图所示： B 点E与点D连接与点B与点C的连接交叉。 因此区域ΩABC~中不存在符合条件的第5个点。 第二种情况：点E在ΩABD、ΩACD、ΩBCD3个区域的任何一个区域，设为区域Ω。 那么必存在A、B、C、D中的一点在区域Ω之外，假设为X点，则点E与点X相连必定要穿越区域Ω，即点E与点X的连接线必与其中的一条连接线交叉。如下图所示：
四色定理 四色定理(Four color theorem)最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德·摩尔根（Augustus De Morgan，1806～1871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。四色问题又称四色猜想，是世界近代三大数学难题之一。 基本介绍 四色问题又称四色猜想、四色定理是世界近代三大数学难题之一。地图四色定理(Four color theorem)最先是由一位叫古德里FrancisGuthrie的英国大学生提出来的。德·摩尔根Augustus De Morgan180618711852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以来数学家们为证明这条定理绞尽脑汁所引进的概念与方法刺激了拓扑学与图论的生长、发展。1976年美国数学家阿佩尔K.Appel与哈肯W.Haken宣告借助电子计算机获得了四色定理的证明又为用计算机证明数学定理开拓了前景。 地图四色定理(Four color theorem)最先是由一位叫古德里Francis Guthrie的英国大学生提出来的。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示即“将平面任意地细分为不相重叠的区域每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”也就是说在不引起混淆的情况下一张地图只需四种颜色来标记就行 发展历史：来自地图的启示 相传四色问题是一名英国绘图员提出来的此人叫格思里。1852年他在绘制英国地图的发现如果给相邻地区涂上不同颜色那么只要四种颜色就足够了。需要注意的是任何两个国家之间如果有边界那么其边界不能只是一个点否则四种颜色就可能不够。 格思里把这个猜想告诉了正在念大学的弟弟。弟弟认真思考了这个问题结果既不能证明也没有找到反例于是向自己的老师、著名数学家德·摩根请教。德·摩根解释不清当天就写信告诉自己的同行、天才的哈密顿。可是直到哈密顿1865年逝世为止也没有解决这个问题。从此这个问题在一些人中间传来传去当时三等分角和化圆为方问题已在社会上“臭名昭著”而“四色瘟疫”又悄悄地传播开来了。 问题的证明一波三折
数学证明方法 什么是数学证明？ 以勾股定理为例，欧几里得几何原本（成书于公元前300年）有一个严格的证明，但巴比仑人在公元前19世纪就已知道了勾股数（13500，12709，18541），中国古代算学利用面积拼凑法，画了几个图让大家看，就算是证明了。因此，勾股定理的知识，并不始于欧几里得的证明，也不终于欧几里得的证明。先有内容，而且人们相信它，后来才有证明。因此， 数学家有自己的追求，别的科学家并不要求严格证明，印度数学家哈里什-钱德拉（Harish-Chandra）曾在大物理学家狄拉克（Dirac）那里做助手，有一次他对狄拉克说，我很苦恼，因为我已找到了问题的答案，却没法证明它。狄拉克的回答是：“我不管什么证明，我只想知道真相！” 让我们再来看数学家是怎样来证明的。英国数学家哈代（Hardy）在1929年写的一篇论文《数学证明》中说道：“严格说来，没有所谓证明这个东西，归根结蒂，我们只能指指点点。”这句话的意思是，数学证明并不是完全形式化的三段论式的推理，数学家不过是指指点点，指手画脚，使读者和听众信服。讲解证明的是人，理解证明的也是人。难怪苏联数学家曼宁（Manin）说：“一个证明只当它通过‘被接纳为证明’这项社会活动后，它才算证明。” 当然，我们可能会问，数学家何必指指点点？老老实实从公理、定理、定义出发进行逻辑推理岂不好？但这做不到。波兰数学家史坦因豪斯（Steinhauss）的一个学生从希尔伯特的几何公理系统出发，证明勾股定理，写下来竟有80页，更令人吃惊的是，如果罗素和怀特黑（A.N.Whitehead）在1910－1913年出版的《数学原理》，从最初的集合概念开始，证明1＋1＝2足足用了300页，这样的证明，谁愿意读？ 计算机辅助证明。我国吴文俊教授给出的机器证明在世界上处于领先的地位，但基本上只能证明初等几何的所有定理，离证明全部数学还远得很。1976年，四色定理的首个证明是一个经典的计算机辅助证明的例子。不少数学家对于计算机证明持谨慎态度，因为很多证明太长，不能由人手直接验证。此外，算法上的错误，输入时的失误甚至计算机运行期间出现的错误都有可能导致错误的结果。 说到这里，似乎都是有关数学证明的“坏话”，那么数学证明的价值何在？首先，数学证明有助于核实真理。数学家的指指点点，是比较严格的，比较符合逻辑的。因而比较可信。其次，数学证明最重要的价值是增进理解，只有弄懂了一个定理的证明，才能真正理解该定理的内容。 对中学数学教育来说，有几点流行的看法需要纠正。中学数学是绝对严格的，中学数学建筑在严格的逻辑推导之上。数学思维能力的核心是逻辑思维能力。真实的情况是，中学数学内容不可能做到绝对严格。中学数学的证明也是“指指点点”，并非三段论式的逻辑演绎。中学数学固然能培养逻辑思维能力，但更重要的是培养学生观察、分析和解决问题的数学观念、数学意识和数学方法。 数学是形式化的思想材料，数学家讲究严密的形式推理，但是学生并不全做数学家，学
四色定理是求解最大值问题以及证明 摘要：问题一：如果任何一个国家与它邻接区域或说国家的染色都是不同的时候，是不是任何两个邻接区域的颜色就是不同的？ 问题二：两个国家的邻接区域还没有什么，但说到三个国家的时候，就有了不同，在其中一个国家看来，另外两个国家都与这个国家是邻接区域，但这两个国家之间有什么关系？一，这两个国家不是相互区域邻接；二，这两个国家是相互区域邻接。四色定理的证明可以从这两个问题出发。 正文： 虽然我们用计算机证明了四色定理，但正如汤米·R·延森和比雅尼·托夫特在《图染色问题》一书中问的：“是否存在四色定理的一个简短证明，……使得一个合格的数学家能在（比如说）两个星期里验证其正确性呢？”【1】 严谨版本的染色问题需要用到拓扑学的概念来定义，那么四色问题的论证是否一定需要拓扑学来证明呢？如果不用拓扑学用其他数学证明，算不算是证明了呢？ 什么是四色定理？ 四色定理是一个著名的数学定理：如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗的说法是：每个地图都可以用不多于四种颜色来染色，而且没有两个邻接的区域颜色相同。【1】 那么不用计算机能不能论证四色定理的成立呢？ 先看一个问题，问题一：如果任何一个国家与它邻接区域或说国家的染色都是不同的时候，是不是任何两个邻接区域的颜色就是不同的？【2】答案是肯定的。这样四色问题就变成了：平面地图上，如果任何一个国家的邻接区域颜色都是不一样的，是不是只要四种颜色就可以全部描述？如果能够证明成立，那么四色定理就是
成立的。 证明如下： 问题二：两个国家的邻接区域还没有什么，但说到三个国家的时候，就有了不同，在其中一个国家看来，另外两个国家都与这个国家是邻接区域，但这两个国家之间有什么关系？一，这两个国家不是相互区域邻接；二，这两个国家是相互区域邻接。 这样三个或者三个以上国家的时候，区域邻接有两种关系：一种是，这个国家的所有的邻接区域国家都与这个国家是区域邻接的关系，但这些国家之间不是相互区域邻接的关系；【注：这里的相互区域邻接指的是完全相互区域邻接，有n个国家，就是n个国家之间是相互区域邻接的。其中一个国家与部分国家区域邻接不算。】二就是，这个国家的所有的邻接区域都与这个国家是区域邻接的关系，同时，这些国家之间还是相互区域邻接的关系。 首先，对不是相互区域邻接的关系的证明。 这一点在《四色定理非计算机的简短证明》中已经证明了，这里简单叙述一下。这里四色定理转化成数学就是函数求解最大值的问题。我们用函数可以解出最大值，论证四色定理的成立。证明： 第一，任何一个国家都是与n个国家相连接的，即与
四色问题的简单证明 一共识 1证明任意地图能不能只用四种颜色就可以填满整个地图，我们可以转换为另一个同等的命题：就是地图上不存在 有五个区域相互接触，最多可能有四块区域相互接触。 2地图分为有空白地图和无空白地图。有空白地图意思是地图的一些区域不需要填色，而无空白地图就是指地图 的每一个区域都要求上色。 二先证明以下三点命题 1一区域要与另一区域接触，那么这一区域的周边要留下空白。（定理一） 证：如下若A要与另一个区域接触的话，那么A的周边 必须留有空白。 若A周边没有空白，而又能与另一块区域接触，这是不 可能的。 2一张无空白地图存在M块区域，对于原有n块无间隙区域，必然有在原有区域的基础上有n+1块区域（n-1<=M） 它们之间无间隙。（定理二） 证；地图上有k块区域无间隙，那么必然有k+1块区域
无间隙。 若有k块区域无间隙，不存在k+1块区域无间隙，除了原来的k块区域外，每一个区域都与这k块区域所组成的图形有间隙。 就是说每一块图形与k块图形有间隙，那么k块区域的周边必然存在间隙，就是地图有间隙（有空白区域）。矛盾。 所以命题成立。 3若无空白的地图的四色问题成立，那么有空白的地图的四色问题也成立。（定理三） 证：对于任意的有空白的地图，我们可以对应地建立无 空白的地图，然后把无空白的地图填满颜色，再根据原 地图除去相应区域的颜色即可。 三主体证明。 （1）首先我们在无空白地图上选取一个区域为研究对象。如下图
（2）由定理二得一定存在一个B 与A 无间隙接触， 并为了A B 都能与另一区域接触依据定理一AB 周边要留有空白，所以有： 这是两区域依照定理一二得到AB 的唯一的关系 即至少需要两种颜色 （3）依据定理二我们在AB 的基础上处在C 使得ABC 之间无间隙， 又因为定理一要ABC 周边留下空白。 舍去c 只与A 或B 接触的 即得 这是在定理一二下的ABC 互相接触的唯一一种关系
四色原理 目录[隐藏] 四色原理简介 四色定理的诞生过程 证明方法 四色定理的重要 德·摩尔根：地图四色定理 利用三角形和数学归纳法证明 [编辑本段] 四色原理简介 这是一个拓扑学问题，即找出给球面（或平面）地图着色时所需用的不同颜色的最小数目。着色时要使得没有两个相邻（即有公共边界线段）的区域有相同的颜色。1852年英国的格思里推测：四种颜色是充分必要的。1878年英国数学家凯利在一次数学家会议上呼吁大家注意解决这个问题。直到1976年，美国数学家阿佩哈尔、哈肯和考西利用高速电子计算机运算了1200个小时，才证明了格思里的推测。四色问题的解决在数学研究方法上的突破，开辟了机器证明的美好前景。 [编辑本段] 四色定理的诞生过程 世界近代三大数学难题之一(另外两个是费马定理和哥德巴赫猜想)。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”,用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这个结论能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。 1852年10月23日，他的弟弟就这个问题的证明请教他的老师、著名数学家德·摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学
家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1 865年哈密尔顿逝世为止，问题也没有能够解决。 1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。 肯普的证明是这样的：首先指出如果没有一个国家包围其他国家，或没有三个以上的国家相遇于一点，这种地图就说是“正规的”（左图）。如为正规地图，否则为非正规地图（右图）。一张地图往往是由正规地图和非正规地图联系在一起，但非正规地图所需颜色种数一般不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规地图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。 肯普是用归谬法来证明的，大意是如果有一张正规的五色地图，就会存在一张国数最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国数，也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。不过肯普的证明阐明了两个重要的概念，对以后问题的解决提供了途径。第一个概念是“构形”。他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻国，不存在每个国家都有六个或更多个邻国的正规地图，也就是说，由两个邻国，三个邻国、四个或五个邻国组成的一组“构形”是不可避免的，每张地图至少含有这四种构形中的一个。 肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证明了只要五色地图中有一国具有四个邻国，就会有国数减少的五色地图。自从引入“构形”，“可约”概念后，逐步发展了检查构形以决定是否可约的一些标准方法，能够寻求可约构形的不可避免组，是证明“四色问题”的重要依据。但要证明大的构形可约，需要检查大量的细节，这是相当复杂的。 11年后，即1890年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题：先辈数学大师们的努力，为后世的数学家揭示四色猜想之谜铺平了道路。 进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。1913年，伯克霍夫在肯普的基础上引进了一些新技巧，美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了5 0国。看来这种推进仍然十分缓慢。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，在J. Koch的
四色定理的简证 一、定义 四色定理：每个平面地图都可以只用四种不同颜色来染色，而且没有两个邻接的区域颜色相同 二、思想 1、归纳演绎 证明平面上五个点彼此两两相连最多可绘制9条两两不相交的连线，以下简称五点问题 2、转化 将四色定理转化为五点问题 三、基本思路 因为平面上四个封闭区域可以两两相邻，所以至少得用四种颜色来为两两相邻的四个区域染色，才能使得相邻的两区域颜色不同。所以要证明一个平面地图是否可以只用四种颜色来染色以使得彼此相邻的两区域颜色不同，只需要证明平面上第五个封闭区域的加入是否可以使得五个封闭区域彼此两两相邻，如若不两两相邻也就证明了四色定理。如果五个区域不能两两相邻，那么六个或六个以上区域也肯定不两两相邻。对于五个以上区域的分析，可以通过区域分离的方式，研究组合中区域之间的关系。因此，只需证明其中五个区域不两两相邻即可 在此证明中，将平面五个封闭区域两两相邻问题转化为五点连线问题----将是否两两相邻转化为五点问题，将封闭区域边界相邻属性通过点线构造抽象化 四、证明五点问题：平面上五个点两两相连最多可画出9条不相交的连线 1、三点情形如图① 如图①平面上3点最多可绘制3条两两不相交的连线 2、四个点的情形 现在再加入一个点，讨论四点情形。若要使得增加的连线最多，显然该点不得落在三条边上，则该点必然在△ABC 内部或△ABC 外部。 分类讨论： （1）当点D 在△ABC 内部时，如图②，此时最多可画出6条； （2）当点D 在△ABC 外部时，如图③，此时最多可画出6条； （3）而图②、图③除形态不一样，本质上是相同的； 3、五个点的情形，不妨取图②用于五点情形的证明 平面上五点可以绘制1025 C 条连线，假设这10条连线是两两不交叉的，那么对于五点连线图形中的任意四点必是两两相连且不交叉的；而四点两两不交叉的图形是唯一的（图②、A C B 图① A C B 图② A C B D 图③ D
“四色定理”简捷证明 王若仲（王洪） 贵州省务川自治县实验学校贵州564300 摘要：1852年，毕业于伦敦大学的格斯里（FrancisGuthrie）来到一家科研单位搞地图着色工作时，发现每幅地图都可以只用四种颜色着色。这个现象能不能从数学上加以严格证明呢？1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题，世界上许多一流的数学家都纷纷参加了四色猜想的大会战。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。就在1976年6月，在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，结果没有一张地图是需要五色的，最终证明了四色定理。我发现“四色定理”还有一种简捷的证明方法，就是利用球面几何的知识来证明“四色定理”。 关键词：四色定理；球面几何；线段；相交 中图分类号：0156 引言 1852年，毕业于伦敦大学的格斯里（FrancisGuthrie）来到一家科研单位搞地图着色工作时，发现每幅地图都可以只用四种颜色着色。这个现象能不能从数学上加以严格证明呢？他和他正在读大学的弟弟决心试一试，但是稿纸已经堆了一大叠，研究工作却是没有任何进展。1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密顿爵士请教，但直到1865年哈密顿逝世为止，问题也没有能够解决。1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题，世界上许多一流的数学家都纷纷参加了四色猜想的大会战。 1878～1880年两年间，著名的律师兼数学家肯普(Alfred Kempe)和泰勒(Peter Guthrie Tait)两人分别提交了证明四色猜想的论文，宣布证明了四色定理。大家都认为四色猜想从此也就解决了，但其实肯普并没有证明四色问题。11年后，即1890年，在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。他指出肯普说没有极小五色地图能有一国具有五个邻国的理由有破绽。不久泰勒的证明也被人们否定了。人们发现他们实际上证明了一个较弱的命题——五色定理。就是说对地图着色，用五种颜色就够了。 不过，让数学家感到欣慰的是，郝伍德没有彻底否定肯普论文的价值，运用肯普发明的方法，郝伍德证明了较弱的五色定理。这等于打了肯普一记闷棍，又将其表扬一番，总的来说是贬大于褒。真不知可怜的肯普律师是什么心情。追根究底是数学家的本性。一方面，五种颜色已足够，另一方面，确实有例子表明
四色定理简易证明 Zhou Yan-hui（周彦辉） （Freelance，Beijing 100070，china） 摘要：首先，证明一个多边形只需要3种颜色就可以保证相邻的边不同 色。然后，将多边形的边换成折线-边界线，结论不变。最后，在地图上任选一个中心区域，以边界线的颜色代表相邻地区的颜色，即可证明只需要4种颜色就可以保证相邻的地区不同色。 关键词：多边形，颜色，折线，国家，地区 1、引言 四色定理是指在地图上只需四种颜色即可将所有的国家和地区分开，或者是相邻的两个国家或地区不能使用同一种颜色，只需要四种颜色就能保证这一点。 四色定理曾经是一个无法证明的定理，后来科学家用计算机经过上亿次验算才得以证明，但是，还有没有更简单的证明方法呢？ 2、任意一个多边形相邻的两条边若不同色，只需3种颜色。 证明： 多边形的两条邻边须用不同的颜色，两条被隔离的边就可以使用同一种颜色。按照这条规则，如果一个多边形的边数是偶数，只需要2种就能保证；如果一个多边形的边数是奇数，则要增加一种颜色，即需要3种颜色（见图一）。图一所示是一个七边形ABCDEFG，唯独“FG”边的颜色是绿色。如果去掉“FG”，就是一个六边形，只需要红、黄两种颜色。 因此，一个多边形要保证相邻两边不同色，只需要3种颜色。 3、要保证两条相邻的边界线不同色，只需3种颜色。 证明： 一个国家的区域由数条边界线围成，将上述的多边形的每条边由直线段变成折线段，类似于地图上凹凸不平的边界线。折线虽然并非直线，似乎有数不清的边，但是，由于每条折线段都有两个端点，相邻的折线同样可以用不同的颜色加以区分。只要不涉及计算折线长度的问题，这个区域仍然可以按多边形处理。由前面的结论推论，要保证相邻的边界线不同色，只需3种颜色（见图二）。 4、地图上相邻的两个国家不能使用同一种颜色，那么，只要4种颜色就能保证这一点。 证明： 在地图上任意取一块地区作为中心区域O，它和周围地区的分界线就构成一个不规则的“多边形”。以每条边的颜色代表相邻地区的颜色，只要保证将邻边的颜色区分开来，就可以将地区之间的颜色分开（见图三）。 根据上面的推论，一个多边形只需要3种颜色，就能保证相邻的边不同色，再加上中心区域的一种颜色，共计4种。即用4种颜色即可将地图上的中心区域和相邻的区域彼此都分开。 由于中心区域的形状是任意的，而且，它的周围任意两个国家或地区都已经
四色原理简介 这是一个拓扑学问题，即找出给球面（或平面）地图着色时所需用的不同颜色的最小数目。着色时要使得没有两个相邻（即有公共边界线段）的区域有相同的颜色。1852年英国的格思里推测：四种颜色是充分必要的。1878年英国数学家凯利在一次数学家会议上呼吁大家注意解决这个问题。直到1976年，美国数学家阿佩哈尔、哈肯和考西利用高速电子计算机运算了1200个小时，才证明了格思里的推测。四色问题的解决在数学研究方法上的突破，开辟了机器证明的美好前景。 四色定理的诞生过程 世界近代三大数学难题之一(另外两个是费马定理和哥德巴赫猜想)。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”,用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这个结论能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。 1852年10月23日，他的弟弟就这个问题的证明请教他的老师、著名数学家德·摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1 865年哈密尔顿逝世为止，问题也没有能够解决。 1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。 肯普的证明是这样的：首先指出如果没有一个国家包围其他国家，或没有三个以上的国家相遇于一点，这种地图就说是“正规的”（左图）。如为正规地图，否则为非正规地图（右图）。一张地图往往是由正规地图和非正规地图联系在一起，但非正规地图所需颜色种数一般不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规地图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。 肯普是用归谬法来证明的，大意是如果有一张正规的五色地图，就会存在一张国数最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国数，也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。不过肯普的证明阐明了两个重要的概念，对以后问题的解决