世界著名数学难题破解
四 色 猜 想 的 证 明
张
彧
典
（山西
盂县 党校
0353-8082346）
摘
要：1879年，肯普（A.B.Kempe）成功地证明了ｄ(Ｖ)=2、3、4时四色猜想成立，但证明ｄ(Ｖ)=5且中心区呈双Ｂ夹Ａ型时，漏证了其中的复杂情形即陷阱构形。本文用色链的数量、位置组合理论找到陷阱构形的一个不可避免解集，从而弥补了肯普（A.B.Kempe）证明中的漏洞。
关键词：链、环、陷阱构形。
Perfecting Of
'A.B.Kempe Proof
'
ZhangYu-dian
(Party School ,Yu County ,Shan Xi 045100)
Abstract:
In 1879 , A.B.Kempe succeeded
in proving Four-color Conjecture when d(v)=2,3,4, but he
neglected much complicated situation (pitfall configuration)
when d(v)=5 and the central area is A placed between B and
B. This paper finds an inevitable set of solutions for the
pitfall configuration use combination of color-chain in
quantity and position,
therefby it makes up the defect of Kempe Proof.
Key
words: Chain;Loop; Pitfall
Configuration.
首先建立四色猜想的数学模型[1]。
1、平面图
用点“· ”
（或小圆圈“〇”
）代表地图上的国家，若两个国家有公共边界，就在代表这两个国家的点（或小圆圈）间连上一条边（线），这样所得到的一张“图”，可以画在一张平面上，其边除在这些点（或小圆圈）上相交外，边和边间无其它交“点”，这样的“图”称为“平面图”。
若用Ｖ代表平面图的点集，用Ｅ代表平面图的边（或线）集，则用Ｇ（Ｖ、Ｅ）代表由Ｖ、Ｅ构成的一张平面图，可简记为Ｇ。
2、色分划、色分图、链和环。
对于平面图Ｇ（Ｖ、Ｅ），用Ｋ种颜色染Ｖ中的每一个点，使得Ｇ中的相邻点具有不同的颜色，就相当于使
k
Ｖ＝ ∪Ｖi
，Ｖi∩Ｖj＝Ф（空集），
i=1
且Ｇ［Ｖi］中无边（i≠j，i，j=1，2，3···，k）。其中Ｇ［Ｖi］表示Ｇ中由Ｖi组成的图，这个图以Ｖi为点集，当Ｖi中的点在Ｇ中相邻时，则它们在Ｇ
[Ｖi]中也相邻。我们称Ｖ的这样一种分划为色分划。
颜色不妨用1、2、3······表示，具有第i种颜色的点集用Ｖi（i=1，2，···）表示，用Ｇi，j表示Ｇ［Ｖi∪Ｖj ］（i，j=1，2，···）， 其中连在一起的部分，称为Ｇi，j的色分图。
在Ｇi，j的色分图中，若由Ｖi，Ｖj 以及连接它们的边排成一个交错序列，则称此序列为联结Ｖi，Ｖj 的一条链，简记为i—j链。若i—j链的两个端点也相邻，则此交错序列为一个环状链，简记为i—j环。
3、肯普构形和陷阱构形
如图1所示：设Ｇ［Ｖi］（i=Ａ、Ｂ、Ｃ、Ｄ）
是Ｇ＇＝Ｇ－Ｖ
的一个色分划，Ｖ及其五个邻点称构形中心区，用五边形表示，其中Ｖ用小圆圈表示，五个邻点染色用Ａ1、Ｂ1、Ｂ２、Ｃ1、Ｄ1表示；并按Ｂ1、Ｂ２夹Ａ1的染色特征把中心区称为双Ｂ夹Ａ型中心区。
再设Ｇ中有以待染色点Ｖ为接口的Ａ1－Ｃ1、Ａ1－Ｄ1环，若它们在中心区外不相交，则称Ｇ为肯普构形[见图1（1）]；若它们在中心区外相交（取一次相交即可），则称Ｇ为陷阱构形，如图1（2）所示，其中二环交集区域边缘上的点用Ａ２、Ｃ２、Ｄ２等表示。其它陷阱构形类同。
在我们所设的陷阱构形中再添加一些不同的色链后，就构成许多不同的标准三角剖分陷阱图。当借助赫伍德颠倒程序[2]对这些标准陷阱图求解时发现，其中色链的不同数量组合和相交组合直接影响其解法上的差异。
现在具体确立解法各不相同却依次递进、相反相成的不可免陷阱构形集合。
如图2：
设图１（２）中有Ｂ1－Ａ２链、Ｂ２－Ａ２链（也可以是Ｄ1－Ｃ２链）存在时。
其解法是：在A1—C1环内“从B1开始交换B、D色点的染色”（简称“作B、D互换”，图中记为“B（D）、D（B）”，其余类推），生成新的A—D环（生不成情形归于下一种构形），再作A—D环外的C、B互换，可给V染C色。
如图3：设图１（２）中有Ｃ1－Ｄ２链、Ｄ1－Ｃ２链存在时。
其解法是：在A1—C1环内作B、D互换，生成B—C环；作B—C环外的D、A互换，生成新的A—C环（生不成情形归于下一种构形）；再作A—C环内的B、D互换，可给V染B色。
如图4：设图１（２）中有Ｃ1－Ｄ２链、Ｂ２－Ａ２链存在时。
其解法是：在A1—C1环内作B、D互换，生成B—C环；作B—C环外的D、A互换，生成B—D环；作B—D环内的A、C互换，生成新的B—C环（生不成情形归于下一种构形）；再作B—C环内的D、A互换，可给V染D色。
如图5：设图4中Ｂ1－Ｄ２链与Ａ1－Ｄ1环相交，这时有Ｂ１－Ａ３、Ｃ１－Ａ３生成。
其解法是：在A1—C1环内作B、D互换，生成B—C环；作B—C环外的D、A互换，生成B—D环；作B—D环内的A、C互换，生成A—D环；作A—D环外的C、B互换，生成新的B—D环（生不成情形归于下一种构形）；再作B—D环外的A、C互换，可给V染A色。
如图6：设图5中Ｃ1－Ｄ２链与Ａ1－Ｃ1环相交，且将Ｃ1－Ｄ２链在Ａ1－Ｃ1环外的Ｄ色点均改染Ｂ色，见图中
。
其解法是：在A1—C1环内作B、D互换，生成B—C环；作B—C环外的D、A互换，生成B—D环；作B—D环内的A、C互换，生成A—D环；作A—D环外的C、B互换，生成A—C环；作A—C环外的B、D互换，生成新的A—D环（生不成情形归于下一种构形）；再作A—D环内的C、B互换，可给V染C色。
如图7：设图6中Ｂ1－Ｄ２链再与Ｂ１－Ａ３链相交，且将Ｂ１－Ａ３链在Ｂ1－Ｄ２链内侧的Ａ色点均改染Ｃ色，见图中
。
其解法是：在A1—C1环内作B、D互换，生成B—C环；作B—C环外的D、A互换，生成B—D环；作B—D环内的A、C互换，生成A—D环；作A—D环外的C、B互换，生成A—C环；作A—C环外的B、D互换，生成B—C环；作B—C环内的D、A互换生成新的
A—C环（生不成情形归于下一种构形）；再作A—C环内的B、D互换，可给V染B色。
如图8：设图7中有Ｂ1－Ｄ２链与Ｃ1－Ｄ２链在Ａ1－Ｃ1环内相交。
其解法是：在A1—C1环内作B、D互换，生成B—C环；作B—C环外的D、A互换，生成B—D环；作B—D环内的A、C互换，生成A—D环；作A—D环外的C、B互换，生成A—C环；作A—C环外的B、D互换，生成B—C环；作B—C环内的D、A互换生成B—D环；作B—D环外的A、C互换，生成新的B—C环（生不成情形归于下一种构形）；再作B—C环内的D、A互换，可给V染D色。
图9：设图8中有Ｂ２－Ａ２链与Ａ1－Ｄ1环相交。
其解法是：在A1—C1环内作B、D互换，生成B—C环；作B—C环外的D、A互换，生成B—D环；作B—D环内的A、C互换，生成A—D环；作A—D环外的C、B互换，生成A—C环；作A—C环外的B、D互换，生成B—C环；作B—C环内的D、A互换生成B—D环；作B—D环外的A、C互换，生成A—D环；作A—D环内的C、B互换，生成新的B—D环；(生不成情形归于下一种构形)再作B—D环内的A、C互换，可给V染A色。
如图10：这是一个十分特殊对称的陷阱构形，即在图3的数量组合的对称图形中，按图6的相交组合方式设C1—D2链与A1—C1环相交，D1—C2链与A1—D1环相交，C1—D2链在A1—C1环外的D色点与D1—C2链在A1—D1环外的C色点均改染B色，见图中
；再设改染成的C—B链、D—B链对称相交。这个陷阱构形就是《赫伍德范例》[2]文中范例2的拓扑变换形式。
对于图10如果沿用图2—9的求解方法，就会产生四个周期转化的陷阱构形，无法得解。但是，四个连续的陷阱构形有一个共同的染色特征，即都包含A—B环，于是产生了如下特殊的张氏链法：
若已知的是第一（或三）图时，先作Ａ—Ｂ环外的Ｃ，Ｄ互换，使得Ａ—Ｃ，Ａ—Ｄ（或Ｂ—Ｃ、Ｂ—Ｄ）二极大链由相交变成相离，简化为肯普构形求解。这里，只取第一图为例，解如图10（1）。
若已知的是第二（或四）图时，先作Ａ—Ｂ环外的Ｃ，Ｄ互换，生成了新的Ｂ—C（或Ｂ—D）链，再作Ｂ—C（或Ｂ—D）链一侧的Ａ，D（或Ａ，C）互换，使五边形五个顶点染色数减少到3。只取第二图为例，解如图10（2）。
下面从理论上证明图2—10组成的不可免解集的完备性。
在已四染色的Ｇ＇中，由Ａ、Ｂ、Ｃ、Ｄ四色中任意二色组成的不同色链共Ｃ42(=6)
种。反映在陷阱构形中，有始点终点均在中心区且相交的Ａ1－Ｃ1环、Ａ1－Ｄ1环，还有始点在中心区，终点在Ａ1－Ｃ1、Ａ1－Ｄ1二环交集区域边缘上的Ｂ1－Ｄ２、Ｂ1－Ａ２（Ｂ２－Ａ２）、Ｂ２－Ｃ２、Ｃ1－Ｄ２（Ｄ1－Ｃ２）四种链。这四种链在陷阱构形中的不同数量组合共四组：
Ｂ1－Ａ２、Ｂ1－Ｄ２、Ｂ２－Ｃ２、Ｂ２－Ａ２
Ｂ1－Ａ２、Ｂ1－Ｄ２、Ｂ２－Ｃ２、Ｄ1－Ｃ２
Ｃ1－Ｄ２、Ｂ1－Ｄ２、Ｂ２－Ｃ２、Ｂ２－Ａ２
Ｃ1－Ｄ２、Ｂ1－Ｄ２、Ｂ２－Ｃ２、Ｄ1－Ｃ２
而六种色链中任意两种色链的不同位置组合共Ｃ６2(=15)