[原创]四色猜测的初步证明（图论法）.

雷明85639720

[watermark]

四色猜测的初步证明（图论法）
雷  明
（二○○九四月）
这里把我于1994年9月27日在陕西省数学会1994年学术年会上所作的关于四色问题的题为《任意图顶点着色色数的界及四色猜测的证明》的学术报告全文发表如下：
任意图顶点着色色数的界
及四色猜测的证明
雷  明
（一九九四年六月五日）
摘要：本文着重研究了任意图顶点着色色数的界，随后再根据平面图结构的特点，进一步证明了四色猜测是正确的。
关链词：四色猜测  图  着色  最小完全同态  色数  密度  平面图  地图  图值函数
一、前言
解决四色猜测的证明问题，关链是在于先要解决好任意图顶点着色色数的界这一问题，即弄清色数与密度的关系。1970年Sachs虽提出了色数一定大于等于密度值，但这只是个下界，上界并没有解决。只有在解决了上述问题之后，才可根据平面图结构上的特点，进一步确定所有平面图色数的总界，也才能使猜测得到证明。
二、图顶点着色色数的界
1、下界
因为任何图的最小完全同态（即顶点数α最少的那个完全同态）的顶点数一定是大于等于密度值ω的，即α≥ω，所以它的色数γ也一定大于等于其密度值，即有：
    γ≥ω                                                                （1）
这就是1970年Sachs提出的任意图顶点着色色数的界，但这只有界而无上界，并不完全。
2、上界
求色数γ的上界就是确定任意图的最小完全同态的顶点数最多能比其密度值大几。由于某个最大团外的任何顶点间均构成的是各种道路，所以就只研究最大团外任一条道路Pn中的各个顶点是否都可以同化到最大团中去即可。
把某一最大团Kω外的任一顶点与该才中所相邻的顶点的数目用a表示（0≤a≤ω－1）这a个顶点构成的集合用Ka表示（Ka包含于Kω），则Kω团外的任何一个团Kn(1≤n≤ω)中各顶点对应的Ka的交集B的界是：
B＝Ka1∩Ka2∩……∩Kan≤Kω－n Kω
否则该图的密度就不是ω最大团也将不是Kω，而是密度比ω大的图了。Kω团与B的差集为：
C＝Kω－B＝Kn Kω
由于任何道路都是由若干个K2团相连接而成的，所以任何一条道路Pn中各顶点对应的Ka的交集为：
    B＝Ka1∩Ka2∩……∩Kan≤Kω－2 Kω
其与Kω团的差集为：
C＝Kω－B＝K2 Kω
（1）当C＞K2时，Kω中至少有三个以上的顶点可供Pn中的顶点同化上去，而对于一条道路来说Kω中只须有两个顶点就足够把该道路中的所有顶点同化到Kω团中去。所以在这种情况下有α＝ω和γ＝ω。
（2）当C＝K2时，有两种情况：
① Pn中只有一个顶点的a＝ω－1，即只有一个Ka＝Kω－1 Kω，这时也有α＝ω和γ＝ω。
② Pn中E 两个以上的顶点的a＝ω－1，这时可把两个这种顶点间（包括这两个顶点在内）的一段看作要研究的道路Pn。
A、当Ka1≠Kan即Ka1∩Kan＝Kω－2 Kω，n为奇数时，Pn中总有一个顶点同化不到Kω中的那个C＝K2上去，即同化不到Kω团中去，但这时该顶点与Kω团中各顶点均有边相邻，所以有α＝ω＋1和γ＝ω＋1（见附图一，a）；n为偶数时，Pn中的全部顶点均可同化到Kω中的那个C＝K2上去，这时则有α＝ω和γ＝ω（见附图一，b）。
B、当Ka1＝Kan即Ka1∩Kan＝Kω－1 Kω，n为奇数时，有α＝ω和γ＝ω（见附图一，c），但n为偶数时，却有α＝ω＋1和γ＝ω＋1（见附图一，d）。
通过上述各点可以看出，图中只要有一条道路中的一个顶点同化不到某一个最大团中去时，就有α＝ω＋1和γ＝ω＋1的关系，决不会比ω＋1更大，最多只可能比ω大1，所以又有：
    γ≤ω＋1                                                             （2）
这就是本文要探求的任意图顶点着色色数的上界。（这一点是不对的，且没有严密的证明。上界应该是γ≤＜1.5ω＞。γ≤＜1.5ω＞的推导证明可参见《数学中国》网上我的《图论方法证明四色猜测》一文。——作者注，2009年2月）
3、色数的界
把公式（1）和（2）综合在一起，可得到：
    ω≤γ≤ω＋1                                                         （3）
这就是任意图顶点着色色数的界。
使得（3）式成立的条件可根据以上分析列表如下：
C＝Kω－B（＝Ka1∩Ka2∩……∩Kan）的值
Pn的奇偶性C＞K2C＝K2
只有一个a＝ω－1顶点的道路有两个以上的a＝ω－1的顶点，则两个这种顶点间可看作要研究的道路
Ka1∩Ka2＝Kω－2Ka1∩Ka2＝Kω－1
N为奇数α＝ω，γ＝ωα＝ω＋1，γ＝ω＋1α＝ω，γ＝ω
N为偶数α＝ω，γ＝ωα＝ω，γ＝ωα＝ω＋1，γ＝ω＋1
三、四色猜测的证明
1、平面图四色猜测的证明
由于任何平面图的密度都小于等于4，即ω≤4，所以
（1）当ω≤3时，按（3）式，其色数决不会大于4，即有：
γ≤ω＋1＝3＋1＝4（ω≤3）
（1）当ω＝4时，按（3）式，是乎有可能色数为5（＝4＋1），但由于平面图结构上的特点，其色数只能是4（γ＝ω）。原因如下：
在上节分析讨论色数的上界时知道，只有当道路Pn对最大团有Ka1∩Ka2∩……∩Kan≤Kω－2，且a1＝an＝ω－1时才可能有γ＝ω＋1＝4＋1＝5，但当ω＝4的图具备这种条件时，就不再是平面图，而是非平面图了，因为这时图中必然会出现交叉边。若把该最大团与这条Pn道路构成的分子图看作一个单图，则其边数e与顶点数v的关系出现了e＞3v－6的情况（见附图二），这显然是非平面图的特征。
综合以上两点，可以得到任何平面图的色数决不会大于4的结论，即有：
γ平≯4或γ平≤4                                                           （4）
到此，平面图四色猜测就得到了证明。
2、具体的平面图的色数及Heawood—图的4—着色
（1）具体的平面图的色数
① ω＝4时，γ＝ω＝4。这是由于ω＝4的平面图的特殊结构所决定的。
②　ω＝3时，有两种情况：
A、含有奇轮时，γ＝ω＋1＝3＋1＝4。因为在奇轮中，任何一个K3团外的其它顶点构成的道路Pn均属于具有Ka1∩Ka2∩……∩Kan≤Kω－2，且a1＝an＝ω－1，Ka1≠Kan，Ka1∩Kan＝Kω－2，n为奇数的情况（见附图三，a）。
B、不含奇轮时，γ＝ω＝3。这时轮中虽具有A中的条件，但n却为偶数（见附图三，b）。
③ω＝2时，也有两种情况：
A、含有奇轮时，γ＝ω＋1＝2＋1＝3。理由同上面②，A（见附图三，c）。
B、不含奇轮时，γ＝ω＝2。理由同上面②，B（见附图三，d）。
④ω＝1时，γ＝ω＝1。这种图只有孤立顶点，一种颜色就可以了。
（2）Heawood—图的4—着色
① 该图是一个平面图，且是极大的，其色数一定不大于4；
② 其密度是ω＝3，并且含有奇轮，色数为γ＝ω＋1＝3＋1＝4；
③ 着色的实践也证明了该图的色数是γ＝4。
（Heawood—图见《图论的例和反例》，其4—着色过程本文作者在1992年陕西省数学会第七次代表大会上作过学术报告，解决了自1890年提出到今未能解决的Heawood—图的4—着色问题，当时着色采用的方法仍是1879年由Kempe创立的方法）
3、地图四色猜测的证明
地图本身就是平面图，它的对偶图仍是平面图，给地图的面（区划）的着色，就是给其对偶图的顶点着色。根据公式（4），其色数一定不地大于4，于是有：
    γ地图≤4                                                               （5）
这就是地图着色的色数。到此，1852年Francis•Guthrie提出的地图四色猜测就得到了证明。
4、地球地图及月球地图的色数
上面讲的地图只能归结为广义地图，它的着色实际上是给平面图的面着色。
（1）地球地图的色数
由地图地球中的区划有一个是海洋，要把这个区划的颜色与其它陆地区划的颜色相区别，就必须增加一种颜色，但这并不影响四色猜测的正确性，因为把地球地图当作平面图而给其面着色时仍只用4种颜色。这时，对于地球地图则有：
　　γ地≤5                                                               （6）
（2）月球地图的色数
由于月球上只有陆地，所以把月球表面无论怎样划分区划时，其地图（月图）的色数仍有：
    γ月≤4                                                               （7）
的关系。这就是月球地图的色数。
四、其他几个有关着色的猜测的证明
图的着色除了顶点着色、面着色外，还有边着色、全着色（边和顶均着色）等，这些着色都可通过对原图的图值函数的顶点着色来实现。
1、边着色的色数与Vizing的线色数的界
边着色也叫线着色，其色数就是原图的图值函数——线图（边图）的顶点着色的色数。由于图的线密度等于原图的最大度Δ，即ω线＝Δ原，把ω线代入公式（3）得线色数的界为：
    Δ≤γ线≤Δ＋1                                                         （8）
这就是1964年Vizing给出的任意图线色数的界。到此，线色数的界也就得到了证明（这里也有误，公式（8）应为Δ≤γ线≤＜1.5Δ＞，可参见《数学中国》网上我的《图的任何着色都可归结为给其
图值函数的着色》一文。——作者注，2009年2月）。
2、全着色的色数与Behzad的全着色猜想
全着色的色数就是原图的另一个图值函数——全图的顶点着色的色数，ω全＝Δ原＋1，所以全着色色数的界为：
    Δ＋1≤γ全≤Δ＋2                                                      （9）
这就是1965年Behzad提出的全着色猜想。当时Behzad只给出了γ全的上界γ全≤Δ＋2，而未给出下界。1971年Vijayditva曾证明了只当Δ≤3时，该猜想才是正确的。而本文给出的Δ却是任意的，而且给出了γ全的下界γ全≥Δ＋1，不但使猜想得到了证明，而且更加完善（这里也有误，公式（9）应为Δ＋1≤γ全≤＜1.5(Δ＋1)＞，可参见《数学中国》网上我的《图的任何着色都可归结为给其
图值函数的着色》一文。——作者注，2009年2月）。
3、根据着色的需要，将会有更多的着色形式及其色数的界
一个图各种图值函数，还有图值函数的图值函数等，所以着色的形式就非常之多。仅管如此，其色数的界同样可以根据公式（3）来确定。例如：平面图的又一个图值函数——整图的色数的界为：
Max（Δ＋1，L＋1）≤γ整≤max（Δ＋1，L＋1）＋1                            （10）
这就是平面图的整着色（顶点、边、面均着色）色数的界。这里L为平面图的周长，即图中最大圈的边数（这里也有错误，周长L应改为面度Δ面，公式则是Max（Δ线＋Δ面）＋1≤γ整≤＜1.5（max（Δ线＋Δ面）＋1）＞，可参见本《数学中国》网上我的《图的任何着色都可归结为给其图值函数的着色》一文。——作者注，2009年2月）。
五、结束语
1、四色猜测是可以用手工证明的，不是“人一辈子的时间也证不完” 的。传统证明所用的方法不大对头，一味的进行着色，从命题本身出发去证明命题是永远也证明不了的。因为图有无穷多个，一个个去着色一辈子时间肯定是着不完的。只有抓住图的结构特征如最大团及结构参数如密度等，通过图的运算如用同化方法求其最小完全同态，得到色数与密度的关系后，结合平面图的特点，问题科很快可以解决，不需要对任何一个图去着色。
2、1976年Appel等人宣称所谓用电子计算机“证明”了猜测，这种说法是错误的，它不能叫做证明，而只叫做验证或着色，因为电子计算机只能按人的意志去着色，且是一个图一个图的着，比如Appel就是用了两千多个特殊的图让计算机着色的，并且同样是沿用了Kempe的着色方法。电子计算机并不会从一般图的结构出发得到色数的界，正如它只会解一元二次方程，但不会得出求根公式一样，它也不会知道一元二次方程一定会有两个根的结论。退一步讲，即就是电子计算机能证明猜测，那么也就说明了人也是能够证明的，因为电子计算机只是一种人造的计算工具，与算盘的作用相同，只是速度快罢了，况且“口诀”、程序都是人编写的，它只是在按人的意志进行工作而已。

雷  明
一九九四年六月五日于金堆城

附图见下页：

附图：

注：图中未画出Ｐn中各顶点与Ｋω团中的a＝ω－2条相邻的
边，只画出了Ｐn的首尾两顶点与C＝K2 Kω的相邻边（图中
Ｋω团中的两个顶点为C＝K2），带箭头的边表示箭尾的顶点向
箭头顶点同化的方向，但这些边在图中是不存在的。
图      一

图     二


图     三
（参考文献略）

雷明85639720

图见DOC原件中