四色定理的简便证法

新齐鲁

四色定理的简便证明

卢玉成   （山东省新泰市实验中学  271200）
在每一张地图上，不论行政区域多么复杂，最多使用四种颜色，就能够给所有有公共边界的不同地区着有不同的颜色加以区别开来，这就是著名的四色定理.下面，我们给出四色定理的一种简便证法.
一、没有公共边界的不同地区
没有公共边界的不同地区，只需要使用同一种颜色就可以区别开来.例如，山东省与黑
龙江省没有公共边界，这两个省可以使用同一种颜色；再如海南省、台湾省以及海域中的诸岛等也可以使用同一种颜色.
二、含有公共边界的不同地区
含有公共边界的不同地区，着有颜色的种数多少与不同地区两两彼此有公共边界的多少有关，两两彼此有公共边界的不同地区越多，着有颜色的种数就越多.
两两彼此有公共边界的含义是指每两个地区都含有公共边界.例如，甲、乙、丙三个不同的地区两两彼此有公共边界，就是说，甲地与乙地有公共边界，甲地与丙地有公共边界，乙地与丙地有公共边界；甲、乙、丙、丁四个不同的地区两两彼此有公共边界，就是说，甲地与乙地有公共边界，甲地与丙地有公共边界，甲地与丁地有公共边界，乙地与丙地有公共边界，乙地与丁地有公共边界，丙地与丁地有公共边界.
地图上的不同地区，我们可以分别用点A，B，C，D，E，…来表示；不同地区所着用的不同的颜色分别用a，b，c，d，…来表示；相邻不同地区的公共边界，用连接两点（表示该相邻的地区）之间的一条线段来表示，并且每条线段的两个端点所表示不同的地区所使用的颜色是不同的，这样，不同地区的着色问题可以看做是不同点的着色问题.
规定1：每两个有公共边界的不同地区，有且只有一条公共边界线，即不存在有三个或三个以上的不同地区共有一条边界线（共用连接点除外），也就是说，两点之间用且只用一条线段来连接.
规定2：连接的所有线段除端点外，既不能重合，也不能相交.
这样我们将上述四色问题可以转化为：
在同一个平面上有m个不同的点，从中任取一个点Pi（i=1，2，…，m）与其余（m-1）个点连接，并且连接任意两点之间的线段除端点外，既不能重合，也不能相交，则在这m个不同的点中，能够两两彼此相连接的点最多有4个.下面我们给出证明.
证明：一个点或多个孤立（互不相连接）的点均可以使用同一种颜色；一条线段有两个端点，这两个端点表示不同的两个地区，该线段表示有公共边界，这样的两个地区，只需要两种不同的颜色即可区别开来.
现在，我们来研究由线段组成的图形.
1. 由n（n为正整数）条线段组成的一条或多条没有封闭的图形
我们知道，每一个端点（或拐点）表示不同的地区，两个相邻的不同地区的公共边界用一条线段来表示，由n（n为正整数）条线段组成的一条或多条没有封闭的图形，其所有端点（所表示的不同地区），可以需要使用a和b两种不同的颜色即可区别开来.如图1和图2所示.

图1

图2
需要特别指出的是在同一条线段（或直线）上的点，如图3所示，当A，B，C三点在同一条线段上时，线段AC与线段AB，BC重合，这意味着他们有两条公共边界线，这与“不同地区有且只有一条公共边界线”矛盾，因此，我们说“连接AB，BC”，此时不能说“连接AC”. 不能说“连接AC”的意思是说地区A和C没有公共边界，他们可以取同一种颜色.

              图3
2.由n（n≥3）条线段组成的一条封闭的图形
（1）当n为奇数时，该图形中的所有顶点（所表示的不同地区），可以需要使用a，b，
c三种不同的颜色即可区别开来，如图4所示.

图4
（2）当n为偶数时，该图形中的所有顶点（所表示的不同地区），可以需要使用a，b两种不同的颜色即可区别开来，如图5所示.
图5
三、在三角形的基础上，增加一个点所构成的图形
从上面的分析来看：一个点只使用一种颜色；一条线段有两个端点，该端点需要使用两种不同的颜色；一个三角形有三个顶点，该顶点需要使用三种不同的颜色.
设存在有三个不同的地区两两彼此有公共边界，即存在不共线的三个点A，B，C连接
成一个三角形，如图6所示，在这个平面上增加一个点D，有如下情况：
      
图6                    图7
由于不同的点表示不同的地区，所以点D与三角形的顶点不能重合，即点D不能在三
角形的顶点处；当点D在△ABC的任一条边上时，不妨假设点D在边AC上，如图7所示，由于线段AC与线段AD，CD重合，这与规定“所有线段不能重合”矛盾，所以点D不能在△ABC的任一条边上.
显然，如果有4个不同的点，其中有三个点A，B，D两两彼此相连接（即A，B，D三点所表示的地区两两彼此有公共边界），也就是说点B与A连接、点B与D连接、点D与A连接；第4个点C与点B 连接，与点D连接，而点C与A不连接 （此时，点A，C所表示的两个不同地区没有公共边界线），且A，D，C三点共线，此时，点A与C可以取同一种颜色（我们可以看作点C在△ABD的外部如图7所示），那么这样的4个点所表示的不同地区，可以使用a，b，c三种不同的颜色就可以区别开来.这样，我们只研究点在三角形的内部和外部两种情况就可以了.
1.当点D在△ABC内部时，如果第4个点D与三角形的三个顶点A，B，C两两彼此相连接，如图8所示，那么所有顶点所表示的不同地区，需要使用a，b，c，d四种不同的颜色就可以区别开来.

图8
2.当点D在△ABC外部时，（1）不妨假设点D在线段AC所在的直线上，即点D，A，C三点共线，如果能够连接DB，DA，那么所有顶点或端点所表示的不同地区，需要使用a，b，c三种不同的颜色就可以区别开来，如图9所示.

图9
（2）不妨假设点D不在线段AC所在的直线上，且点D与B在线段AC所在直线的两侧，如果能够连接DA ，DB，DC，且线段DB与线段AC不相交，那么所有顶点（或端点）所表示的不同地区，需要使用a，b，c，d四种不同的颜色即可区别开来，如图10所示；若能够连接DA，DC ，当连接DB时，线段DB与线段AC有可能“相交”，则所有顶点（或端点）所表示的不同地区，需要使用a，b，c三种不同的颜色即可区别开来，如图11所示.
            
图10                            图11
    （3）不妨假设点D不在线段AC所在的直线上，且点D与B在线段AC所在直线的同侧，如图12和图13所示，此时，结果与（2）类似，不必赘述.
         
                  图12                          图13
由上述所知，如果每4个点满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的4个点所表示的不同地区，只需要使用a，b，c，d四种不同的颜色即可区别开来.
四、在如图8所示的基础上，增加一个点所构成的图形
我们从上面的分析可以得到一般结论：在同一个平面上，存在3个点，如果满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的3个点所表示的不同地区，需要使用三种不同的颜色；在同一个平面上，存在4个点，如果满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的4个点所表示的不同地区，需要使用四种不同的颜色.
我们自然要问：在同一个平面上，存在5个点或5个以上的点，如果满足两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交，那么这样的5个点或5个以上的点所表示的不同地区，就需要使用五种或更多种不同的颜色吗？回答是不可能的.这是因为，在同一个平面上，有5个点或5个以上的不同点是不可能存在两两彼此相连接，且连接的所有线段除端点外，既不能重合，也不能相交的，从而说明，在同一个平面上，不存在超过四种不同的颜色.我们给出如下推理：
如图8所示中，再增加一个点E，共计5个点，有如下几种情况：
（1）如果第5个点E落在△ABC的外部，那么点E与△ABC内部的点D不能够连接.假设点E与D能够连接，由于△ABC是一个封闭的图形，一个点E在△ABC的外部，一个点D在△ABC的内部，当连接ED时，必然与△ABC中的某一条边相交，这与规定（所有的线段不相交）矛盾，所以说尽管点E能够与点A，B，C两两彼此相连接，但点E与点D不能够连接，因此，5个不同的点两两彼此不能够相连接.此时，点E和点D可以使用同一种颜色着色，这样的5个不同点所表示的不同地区，可以需要使用a，b，c，d四种不同的颜色就可以区别开来，如图14所示.
           
图14                           图15
（2）如果第5个点E落在△ABC的内部，那么点E必然会落在△ABC内部中△ABD，△BCD和△ACD三个三角形中的某一个三角形的内部，不妨假设点E落在△ABD的内部，如图15所示，此时，点C在△ABD的外部，由（1）知点E与C不能够连接，因此，5个不同的点两两彼此不能够连接.此时，点E与C可以使用同一种颜色着色，这样的5个不同的点所表示的不同地区，可以需要使用a，b，c，d四种不同的颜色就可以区别开来.
由上述所知，5个不同的点两两彼此不能够连接，这就是说，在同一个平面上，尽管由原来不同的4个点增加到5个点，多了一个点，但颜色的种数并没有增加，这是因为有一对点不能连接，该两点所表示的不同地区可以取同一种颜色，即存在有1对点着色相同，此时，仍然需要使用a，b，c，d四种不同的颜色就可以区别开来.
五、在如图15所示的基础上，增加一个点所构成的图形
如图15所示中，再增加一个点F，共计6个点.
1．如果第6个点F在△ABC的外部，那么点F与△ABC内部的点E或D不能够连接，也就是说，6个不同的点两两彼此不能够连接，如图16所示.新增加的点F的着色可以取与点D的颜色相同（新增加一对着色点）；点E的着色可以取与点C的颜色相同（原有的一对着色点），这样共有2对相同的着色点，这说明颜色的种数并没有增加，仍然需要使用a，b，c，d四种不同的颜色就可以区别开来.

图16
2．如果第6个点F在△ABC的内部，那么点F必然会落在△ABE，△BED，△AED，△BCD，△ACD这5个三角形中的某一个三角形的内部.不妨假设点F落在△BDC的内部，如图17所示.显然，新增加的点F与A不能够连接，他们可以取相同的颜色（新增加一对着色点）；点E与C不能够连接，他们可以取相同的颜色（原有的一对着色点），这样存在2对相同的着色点，因此，6个不同的点两两彼此不能够连接. 也就是说，尽管由5个不同的点增加到6个不同的点，又多了一个点，但颜色的种数并没有增加，这是因为有2对点着色相同，此时，仍然需要使用a，b，c，d四种不同的颜色就可以区别开来.

图17
类似地，第k（5≤k≤m）个点落在如图8所示的图形中，（1）如果第k个点落在△ABC的外部，那么第k个点与△ABC的内部的某一点不能够连接，因此，有k个点两两彼此不能够连接，同时可以看出，第k个点可以取与△ABC的内部的某一对应点（不能连接）的着色的颜色相同，这样颜色的种数没有增加，第k个点的情形与第（k-1）个点的情形的着色相同；（2）如果第k个点落在△ABC的内部，那么必然会落在且只能落在△ABC被分割成（2k-5）个不重叠三角形中的某一个三角形的内部，此时，该点与该三角形的外部的点不能够连接，且有（k-4）对点（不能连接的）着有对应相同的颜色，这说明颜色的种数并没有增加.
总上所述，在同一个平面上，超过4个不同的点，两两彼此不能够连接，这就是说能够两两彼此连接的点最多有4个，所以，在一张地图上的所有有公共边界的不同地区，最多使用四种不同的颜色就可以加以区别开来，四色定理成立.证毕.
我们根据上述判定方法来诠释中国政区地图，为何最多使用四种不同的颜色.
在《中华人民共和国地图》（人民交通出版社，2003年8月第3版）上，因为最多有4个不同地区（省）两两彼此有公共边界，这4个省两两彼此有公共边界的地区分别是宁夏回族自治区、内蒙古自治区、甘肃省和陕西省，即甘肃省与内蒙古自治区有公共边界，甘肃省与陕西省有公共边界，甘肃省与宁夏回族自治区有公共边界；内蒙古自治区与陕西省有公共边界，内蒙古自治区与宁夏回族自治区有公共边界；陕西省与宁夏回族自治区有公共边界.换句话说，如果把这4个不同地区分别看成A，B，C，D四个不同的点，由于它们两两彼此有公共边界，也就是说这4个不同点能够两两彼此相连接.如图8所示，甘肃省相当于点B，内蒙古自治区相当于点A，陕西省相当于点C，该三点A，B，C能连接成一个三角形，宁夏回族自治区相当于△ABC的内部的一个点D，根据上面得到的结论，可以判断这张《中华人民共和国地图》的着色，最多使用a，b，c，d四种不同的颜色就可以绘制而成. 见附件一：《中国政区四色地图》着色分布图.
再如，在《世界地图》（人民交通出版社，2003年8月第3版）上，我们看到有公共边界的国家，最多有巴拉圭、巴西、玻利维亚及阿根廷这4个国家两两彼此有公共边界（还有坦桑尼亚、莫桑比克、赞比亚和马拉维4个国家两两彼此有公共边界），它们分别用4个不同的点来表示，则这4个点之间两两彼此相连接，根据上面得到的结论，可以判断这张《世界地图》也需要使用a，b，c，d四种不同的颜色，就能够保证相邻国家着有不同的颜色加以区别开来（图形略）.
顺祝
安康！

作    者：卢玉成   
Q     Q：504526000
电子信箱：luyucheng@126.com     
单    位：山东省新泰市实验中学
邮    编：271200   
地    址：山东省新泰市实验中学杏山路335号                     
2012年4月16日



发表在《数学学习与研究》2012年第7期 126页






附件一：方案不唯一，仅供参考.
中国政区四色地图

我们如果用a，b，c，d 分别表示四种不同的颜色，那么不同地区的着色可以分别记成：着有a色的地区有新疆，陕西，安徽，湖南，云南以及海洋；着有b 色的地区有黑龙江，辽宁，山东，山西，浙江，广东，贵州，甘肃，西藏；着有c色的地区有宁夏，吉林，河北，福建，江苏，湖北，四川，广西；着有d色的地区有内蒙古，青海，重庆，河南，江西；没有公共边界的海南和台湾及其海洋中的诸岛均可取同一种颜色（可以取不同于a色绘制），如选d色；上海市可以取 d色；北京市可以取a色；天津市可以取d色；香港或澳门可以取d或c色.
背景材料：
四色问题，首先由英国人格斯里克（F.Gathril）于1852年10月23日向英国数学家摩根请教过；1840年德国几何学家莫比乌斯以假说的形式向他的学生提出过这个问题；德国数论专家闵可夫斯基（Minrowsri, 1864－1909）在大学给学生上拓扑课时也论证过，至今“四色问题”困扰人们已有100多年，都没有圆满解决。有消息说，1976年6月美国数学家阿沛尔与哈肯（Kenneth Appel与Wocfgang Haken）借助于两台不同的电子计算机，工作了1200个小时，做了100亿次判断证明了“四色问题”称为“四色定理”。该定理已载入了《数学小词典》（陈通鑫等编。测绘出版社，1982，北京）中，但是，2004年11月薛更法著文《四色猜想》说：“不久前出版的文献援引数学界权威人士的话说：传说的‘四色问题’获证的消息不确实”（〈学习方法报〉。2004年第44期，山西）。人们对“四色问题”的证明是否彼此起伏，说法不一。“四色问题”尽管得到了计算机证明，人们还是希望用简捷明快的方法得到数学的证明。

APB先生