四色定理的简便证明

卢玉成

在每一张地图上，不论行政区域多么复杂，最多使用四种颜色，就能够给所有有公共边界的不同地区着有不同的颜色加以区别开来，这就是著名的四色定理.下面，我们给出四色定理的一种简便证法.

一、没有公共边界的不同地区

没有公共边界的不同地区，只需要使用同一种颜色就可以区别开来.例如，山东省与黑龙江省没有公共边界，这两个省可以使用同一种颜色；再如，海南省、台湾省以及海域中的诸岛等也可以使用同一种颜色.

二、含有公共边界的不同地区

含有公共边界的不同地区，着有颜色的种数多少与不同地区两两彼此有公共边界的多少有关，两两彼此有公共边界的不同地区越多，着有颜色的种数就越多.

两两彼此有公共边界的含义是指每两个地区都含有公共边界.例如，甲、乙、丙三个不同的地区两两彼此有公共边界，就是说，甲地与乙地有公共边界，甲地与丙地有公共边界，乙地与丙地有公共边界；甲、乙、丙、丁四个不同的地区两两彼此有公共边界，就是说，甲地与乙地有公共边界，甲地与丙地有公共边界，甲地与丁地有公共边界，乙地与丙地有公共边界，乙地与丁地有公共边界，丙地与丁地有公共边界.

地图上的不同地区，我们可以分别用点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为正整数）条线段组成的一条或多条没有封闭的图形，其所有端点（所表示的不同地区），可以需要使用a和b两种不同的颜色即可区别开来.如图1和图2所示.

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

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

图9

2.当点D在△ABC外部时，（1）不妨假设点D在线段AC所在的直线上，即点D，A，C三点共线，如果能够连接DB，DA，那么所有顶点或端点所表示的不同地区，需要使用a，b，c三种不同的颜色就可以区别开来，如图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所示，此时，结果与②类似，不必赘述.

图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

图17

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四种不同的颜色就可以区别开来.

类似地，第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四种不同的颜色，就能够保证相邻国家着有不同的颜色加以区别开来（图形略）.

附件一：方案不唯一，仅供参考.

我们如果用a，b，c，d分别表示四种不同的颜色，那么不同地区的着色可以分别记成：着有a色的地区有新疆、陕西、安徽、湖南、云南以及海洋；着有b色的地区有黑龙江、辽宁、山东、山西、浙江、广东、贵州、甘肃、西藏；着有c色的地区有宁夏、吉林、河北、福建、江苏、湖北、四川、广西；着有d色的地区有内蒙古、青海、重庆、河南、江西；没有公共边界的海南和台湾及其海洋中的诸岛均可取同一种颜色（可以取不同于a色绘制），如选d色；上海市可以取d色；北京市可以取a色；天津市可以取d色；香港或澳门可以取d或c色.