摘要：Kempe给出的证明被Heawood举出一个反例推翻。本文分析了Heawood的反例，指出了Heawood反例中直接采用Kempe换色方法存在的矛盾。通过对Heawood反例的第二次换色条件的分析，进一步利用Kempe换色方法，成功证明了了“四色定理”。
关键字：图论 平面图
MR分类号：05C15
1 引言
“四色定理”又称“四色猜想”，一个多世纪以来，激发了大量的数学专家和爱好者的研究[1][2]。众多数学家花了100多年的时间要证明这个听起来十分简单的猜想，结果均以失败告终。1890年，P.J.Heawood指出了Kempe证明中的错误，采用Kempe的“色交换技术”，证明了“五色定理”。1976年7月，美国伊利诺大学的两位数学家Kenneth Appel和Wolfgang Hanken用计算机证明了“四色猜想”成立。借助于机器证明“四色定理”是现代计算机应用所取得的一个重大的成就，但由于问题的简单和证明的复杂，使得此证明显得不十分理想。本文分析了Heawood给出的反例，指出了直接采用Kempe换色方法存在矛盾导致Kempe换色失败。通过对Heawood反例的第二次换色条件的分析，进一步利用Kempe换色方法，证明了“四色猜想”的成立。
2 Kempe证明及Heawood反例
Kempe通过引入不可免完备集F ={O,P,Q,R}（图1），采用色交换，“证明”最小图G不存在来证明四色定理。但是在证明G不含构型R时，由Heawood给出了反例（图2）[2]，从而发现了Kempe证明中的漏洞。
v
v
P
v
v
Q
O
图1 Kempe证明中的不可完备集
例如，设NG(v)={v1,v2,v3,v4,v5},π=(Vb,Vr,Vy,Vg)是G-v的一种4染色，图中字母b,r, y,g表示四种不同的颜色。v2和v4在Gb,g中是连通的，v2和v5在Gb,y中也是连通的。因此无论交换Gb,g中的颜色还是交换Gb,y中的颜色，都不能空出一种颜色来给v。v1和v4在Gr,g中不连通，因此可以考虑交换Gr,g含v1分支中的颜色（图中括号中的颜色）。但π(v3)=r，因此不能空出颜色来染点v。又因v3和v5在Gr,y中不连通，所以考虑交换Gr,y含v3分支中的颜色。于是v3被染上y。颜色r虽被空出来了，但此时相邻两顶点6和7都被换成颜色r。由此说明Kempe的证明中包含了一个漏洞。
接下来本文首先分析了Kempe对G不含构型Q的证明，然后分析Heawood反例，最后给出新的证明。
3 Kempe对G不含构型Q
考察图3，如果顶点v1,v2,v3 ,v4只用了少于四种的染色，显然把第四种颜色对v染色。假若不然，那么v1,v2,v3 ,v4使用了四种颜色，设为b,r, y,g。如果v1和v3在Gr,y中不是连通的，那么可以考虑交换Gr,y分支中的颜色（含v1分支或含v3分支都可以），从而空出一种颜色对v染色。否则，那么Gr,y+v构成一个圈，从而v2,v4在Gb,g中不连通，可以换色，从而空出一种颜色对v染色。
由上述证明，我们可以得到如下引理：
引理1：如果图G的三个顶点v1,v3 ,v4采用三种颜色染色且在各自的两色导出子图中都连通，从而其中必存在一个顶点，与染第四种颜色的第四个顶点在其两色导出子图中不连通。这是证明G不含构型Q的本质。
6
图2 Heawood反例
v4(g)
v1(r)
v2(b)
v3(y)
v
图3
4 Heawood反例分析
在Heawood反例中，v2和v4在Gb,g中是连通的，v2和v5在Gb,y中也是连通的，所以不能对它们进行换色。根据引理一，显然v1,v3必分别与其中的一个顶点在其两色导出子图不连通，即v1,v4和v3, v5在Gr,g和Gr,y中不连通。Kempe的做法是分别对其换色，从而得到“证明”。而Heawood反例指出，分别换色后可能得到矛盾的结果。那么其原因在哪儿呢？
通过考察图2，我们发现，在经过第一步换色之后，其实是得到了一个新的图，只不过某些顶点的颜色发生了变化，但仍然保持为4染色。这个恰恰是Kempe证明中没有考虑的问题！Kempe没有考察新图，想当然的仍然采用原图的办法进行换色。Heawood抓住这一点指出了其中的问题。如图所示，第一换色完成后，新得到的图中，v3和v5在Gr,y中的关系发生了变化，已经从不连通变为连通了。显然，如果仍旧按照原图换色，必将得到矛盾。
因此，有必要考察第一次换色完成后新的图的性质，从而得到如下证明。
5 四色证明
假设图G含有构型R，则染色方式有两种情况，如图4(a)和4(b)所示，字母b,r, y,g表示四种不同的颜色。如果在v2,v4,v5三个顶点中存在两个顶点在其两色导出子图中不连通，则可以通过换色，空出一种颜色给v。否则v2,v4,v5在其两两两色导出子图都连通。根据引理1，对于v1和v3，在v2,v4,v5中分别存在一个顶点，在其各自的两色导出子图中不连通。如果它们对应于同一个顶点，那么只能如图4(a)所示，此顶点为v4。显然可以同时实施换色（对v1和v3所在分支。如果v1和v3连通，则一次换色就可成功），空出g颜色给v。
否则，v1和v3分别对应不同的顶点，那么只能如图4(b) 所示，其中v1和v4在Gr,g中不连通，v3和v5在Gr,y中不连通。第一步操作，交换Gr,g含v1分支中的颜色，得到新的图G’。考察图G’，如果v3和v5在G’r,y中仍旧不连通，那么可以交换G’r,y含v3分支中的颜色。这样空出颜色r给v。否则，v3和v5在G’r,y中变成连通的了，这个时候就不能再进行换色（这正是Heawood反例的情况）。但是现在，考察G’r,y+v，现在已经是一个圈了，对于顶点v2,v4，已经从Gb,y中连通变成了G’b,y中的不连通。显然对于G’b,y可以进行换色（对含v2或v4的分支都可以），从而空出一种颜色染v。因此得到图G可染色，从而不存在构型R。四色定理得证。
现在我们分析在什么样的情况下会导致v3和v5在G’r,y中的关系发生了变化。第一步换色操作，把Gr,g含v1分支中的r和g颜色进行了交换，导致v3和v5在G’r,y中连通。显然子图G’r,y没有颜色g的顶点，因此必有一个r色顶点是从换色操作得到的。又由于与r色顶点相邻的顶点颜色只能是y，由此推断在原图G中，在子图Gr,g的v1分支中必存在一个g色顶点，在其相邻顶点中存在两个y色顶点，其中一个y色顶点在Gr,y的含v3分支中，另一个y色顶点在Gr,y的含v5分支中。对于Heawood反例图2来说，这个顶点就是7顶点。
v4(g)
v1(r)
V5(y)
v
v2(r)
v3(b)
v4(g)
v1(r)
V5(y)
v
v2(b)
v3(r)
6 结论
通过上面的分析，我们可以毫无疑问的说，“四色定理”是成立的。而问题的关键则是对Kempe换色方法的进一步应用。
[1] 徐俊明, 图论及其应用, 合肥：中国科学技术大学出版社，1998
[2] 王树禾, 图论, 北京：科学技术出版社，2004
本文地址：http://com.8s8s.com/it/it24964.htm