四色猜测证明方法集锦（整理稿）（一）

雷明85639720

四色猜测证明方法集锦（整理稿）（一）
雷  明
（二○一五年五月二十四日）

我一直主张用“不画图，不着色”的方法解决四色问题。因为图是无穷多的，永远也画不完。赫渥特否定坎泊的证明，以及前二十多年米勒对自已的想法的放弃，都说明了因为他们对自已所构造的图不能4—着色而对坎泊的证明和米勒自已的想法进行了否定。象这样否定来，否定去，何时才能到头呢。没完没了的，猜测永远也是证明不了的。
鉴于赫渥特对坎泊的否定，我在一九九二年就提出了“不画图，不着色”解决四色问题的设想。几十年来，我通过对图论以及拓扑学的研究，现在完全可以做到这一点，而且证明的方法是多种多样的。现在我把它们整理如下：
一、“不画图，不着色”证明四色猜测的原理
图的色数γ＝图的最小顶独立集数β＝图的最小完全同态的顶点数α。图的最小完全同态的亏格n同态一定小于等于原图的亏格n原图。图的色数γ大于等于图的密度ω，而小于等于图的密度的一倍半，即ω≤γ≤1.5ω。色数大于图的密度的原因是图中存在着对于某一个最大团来说的不可同化道路，而相互间有联存在的不可同化道路的条数S是受着双重制约的，即S既要不大于密度ω的一半，又要不大于与图同亏格的曲面所能嵌入的最大完全图的顶点数V与图的密度ω的差，即S≤ω/2且S≤V－ω。
1、图中不相邻的顶点可着同一颜色，也可以划分到同一个顶独立集内，还可以同化（把两个不相邻的顶点凝结到一起的过程叫同化）成一个顶点；
2、任何图同化的最后结果都一定是一个完全图，这就叫图的完全同态。而一个图并不只有一个完全同态，如道路P4的完全同态就有两个，一个是K3（把顶点1 和4同化在一起），另一个是K2（把顶点1 和3同化在一起，把顶点2和4同化在一起）。把一个图的所有完全同态中顶点数最少的那一个就叫做图的最小完全同态；
3、同化时，要能够得到图的最小完全同态，就必须遵循一个原则，这就是进行同化的两个顶点间的距离一定要是最小的，即在该两顶点间只能有一个顶点相隔，这样就可以保证所得到的完全同态是最小的，即其顶点数是最少的；
4、图的最小完全同态中的任何一个顶点都是由图中若干个互不相邻的顶点同化而来，它们就构成了一个顶独立集，这些顶点着同一种颜色是完全可以的；
5、图的最小完全同态有几个顶点，这个完全同态着色就得用几种颜色，把这个着了色的完全同态的各顶点，按照同化时的相反方向、连同其已着的颜色一起，再反回到在原图中的位置，一个图的着色就完成了。图中一定不会存在相邻顶点着同一颜色的情况；
6、可以得出结论，图的色数就等于图的最小完全同态的顶点数，求一个图的色数就等于求该图的最小完全同态的顶点数。要证明四色猜测，就相当于只要证明了任意平面图的最小完全同态的顶点数不大于4就可以了；
7、图的亏格是其可嵌入的曲面的最小亏格，那么亏格是n的图一定是可嵌入在亏格为n的曲面上的图。图的同化是在亏格为n的曲面上进行的，最后得到的最小完全同态也一定是嵌入在亏格是n的曲面上的图。比如K5图的亏格是1，其最小完全同态就是原图K5本身，其亏格也应是1；而K3,3图的亏格也是1，但其最小完全同态却是K2，虽然这个K2现在仍是嵌入在亏格为1的曲面上，但K2的亏格却是0（K2不但能嵌入亏格为1的曲面，也能嵌入亏格为0的曲面，小者是0，所以K2的亏格是0）。这就说明图的最小完全同态的亏格一定是小于等于原图的亏格的；
8、假设一个任意图的最小完全同态的亏格是大于原图的亏格的，那么该完全同态可嵌入的曲面的最小亏格就应该比原图可嵌入曲面的最小亏格大，但我们对它的同化仍是在原亏格的曲面上进行的，这时的最小完全同态根本不可能再嵌入到一个更大亏格的曲面上去。所以图的最小完全同态的亏格是不可能大于原图的的亏格的。如果说最小完全同态的亏格大于原图的亏格，那么在把最小完全同态按原同化时的相反方向再返回原图时，这时就将是一个嵌入在比原来亏格大的曲面上的图。但这是绝对不可能的，因为在同化和还原时都是在同一个曲面上进行的，其亏格是不会发生变化的；
9、根据以上的结论，任何亏格为n＝0的平面图的最小完全同态的亏格也一定仍然是等于0的，也即任何平面图的最小完全同态一定都是平面图。要证明四色猜测，就相当于证明平面图中的完全图着色时，色数不大于4 也就可以了；
10、任何图中都有一个最大团，把最大团的顶点数叫做图的密度。由于最大团中的顶点均是相邻的，不可能再进行同化，所以图的色数一定是不小于图的密度的。由于有5—圈（密度是2）同化的结果是K3图和5—轮（密度是3）同化的结果是K4，出现了最小完全同态的顶点数比原图中最大团的顶点数大的情况，所以图的色数一定是大于等于图的密度的；
11、只所以有最小完全同态的顶点数大于最大团的顶点数的情况，是因为有顶点同化不到最大团中去。只所以有这样的不可同化顶点，又是因为有不可同化道路，该道路无论怎样同化，总是有一个顶点同化不到最大团中去的。如5—圈中的任何一个K2团以外的顶点，5—轮中的任何一个K3团以外的顶点，都对该K2团和K3团构成了一条不可同化道路；
12、从上面所说的5—圈和5—轮的结构上看，不可同化道路中的任何一个顶点都与最大团中的ω－2个顶点相邻，另外该道路的两个端点顶点又与最大团中剩下的两个顶点之一相邻，这就产生了该道路中总有一个顶点同化不到最大团中去的情况，使得图的最小完全同态的顶点数有大于最大团的可能；
13、对于某个最大团来说，有一条不可同化道路，就有一个顶点同化不到最大团中去，但当若干条不可同化道路未构形联时，均可把各道路中不相邻的顶点作为不可同化顶点，然后还可以再把这些不可同化顶点同化在一起。所以没有构成联的不可同化道路再多，也只能相当于只有一条的情况，只可能有一个顶点同化不到最大团中去；
14、如果对于某一个最大团有S条不可同化道路，且其间均已构成了联，这时由于联中任何一条道路中的各个顶点均与其他道路中的各个顶点均相邻，S个不可同化顶点不可能再同化成一个顶点，所以就有S个顶点同化不到最大团中去；
15、由于不可同化道路所构成的联只是图中的一个分子图，当然联本身的密度也一定不会大于图的密度。因为联的密度是2S，即是由每条不可同化道路各提供两个顶点所构成的团的顶点数。这个2S一定是不能大于图的密度的，这就使得构成联的不可同化道路的条数S受到一定的约束。所以又有2S≤ω和S≤ω/2的关系，也有最小完全同态的顶点数最大只可能是ω＋S＝α≤ω＋ω/2≤1.5ω，也有ω≤α≤1.5ω和ω≤γ≤1.5ω的关系；
16、亏格为n的图的最小完全同态的亏格是小于等于原图的亏格的，而原图所嵌入的曲面也有可以嵌入其上的最大完全图，这个最大完全图的顶点数也对可嵌入该曲面上的图的最小完全同态的顶点数是有所限制的。若令这个最大完全图的顶点数为V,则可嵌入该曲面上的图的最小完全同态的顶点数最大也只能是V，即有图的密度加不可同化道路的条数，是不会大于这个最大完全图的顶点数V的，即ω＋S≤V,有S≤V－ω的关系。可见任何图中不可同化道路的条数是受着双重制约的，即S≤ω/2且S≤V－ω，即S既要不大于ω/2，又要不大于V－ω；
17、虽然米歇尔斯基操作（简称M—操作）的结果得出了“存在无三角形而色数是任意大的图”的结论，但这并不影响对四色猜测的证明。因为除了K1图（独立顶点），K2图（P2道路），K3图（C3圈），P3道路，在进行了一次M—操作后的图是平面图外，其他平面图进行了一次M—操作后的图均是非平面图，均不再是四色问题所研究的对象了。以上几个平面图在进行了第二次M—操作后，也都成为了非平面图，也不是四色问题研究的对象了。这些图中最大的团是K3团，即就是进行了一次M—操作，其色数也只能比其密度增大1，而变成4，但仍没有大于4。所以说M—操作是不会影响四色猜测证明的。
二、多种“不画图，不着色”证明四色猜测的方法
（1）用多阶曲面上图的欧拉公式进行证明
设一个亏格为n的图同化后所得到的最小完全同态是Kv，该同态是一个顶点数是v的完全图。该Kv一定是能够满足多阶曲面上图的欧拉公式v＋f－e＝2（1－n）的。因为任意图中都有3f≤2e的关系，把f≤2e/3带入以上的欧拉公式中得
     3v－e≥6－6n
再把完全图中边与顶点的关系e＝v（v－1）/2代入上式得
        v2－7v＋12（1－n）≤0
解这个关于完全图（即亏格为n的图的最小完全同态）的顶点数v的一元二次不等式，得正根是
v≤（7＋√（1＋48n））/2
由于顶点数必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞
式中用＜ ＞表示其中的数字向下取整。因为完全图的色数就等于其顶点数，所以又有
γ≤＜（7＋√（1＋48n））/2＞
这就是赫渥特的地图着色公式。当n＝0时，上式的计算结果是γ≤4，这就是四色猜测。四色猜测得证是正确的。
（2）用平面图欧拉公式直接求平面图的色数
由于亏格为0的平面图的最小完全同态的亏格仍然是一个亏格为0的平面图，因此平面图的欧拉公式v＋f＝e＋2也一定是适用于平面图的最小完全同态的。把任意图中面与边的关系3f≤2e代入平面图的欧拉公式中得
    3v－e≥6
再把完全图的边与顶点的关系e＝v（v－1）/2代入其中得
        v2－7v＋12≤0
解这个关于平面图最小完全同态的顶点数v的一元二次不等式得
        v1≤4和v2≤3
其中v1≤4包含v2≤3，所以该不等式只有一个根v1≤4，即任何平面图的最小完全同态的顶点数都是小于等于4的。
     因为任何图的色数都等于其最小完全同态的顶点数，所以有平面图的色数也是小于等于4 的结论。这就是四色猜测。四色猜测也得到证明是正确的。
（3）用完全图的边与顶点的关系直接求平面图的色数
亏格为0的平面图的最小完全同态仍是一个亏格为0的平面图，它的顶点数就是该平面图的色数。而亏格为0 的平面图中的完全图只有K1，K2，K3和K4四种。
已知完全图的边与顶点的关系是
e＝v（v－1）/2
同时又要符合任意平面图中边与顶点的关系
e≤3v－6
令以上两式相等，即有
        v2－7v＋12≤0
解这个关于平面图最小完全同态的顶点数v的一元二次不等式得
        v1≤4和v2≤3
其中v1≤4也包含v2≤3，所以该不等式只有一个根v1≤4，即任何平面图的最小完全同态的顶点数都是小于等于4的，也即任何平面图的色数一定是小于等于4的。这就是四色猜测。四色猜测得到证明是正确的。
（4）用平面图的最小完全同态仍是平面图来证明
由于任何图的最小完全同态的亏格都是小于等于原图的亏格的，所以亏格为0的平面图的最小完全同态的亏格仍然是0，也就是说平面图的最小完全同态仍然是平面图。而平面图中的完全图只有K1，K2，K3，K4四种。其顶点数分别是1，2，3和4，都不大于4。由于图的色数等于其最小完全同态的顶点数，所以也有平面图的色数都是不会大于4 的结论。这也就证明了四色猜测是正确的。
（5）用各密度的图的最小完全同态的顶点数不大于同亏格图所能嵌入的最小曲面的最大完全图的顶点数来证明
有联存在的不可同化道路的条数S是不大于密度ω的一半，也不大于该亏格下的最大完全图的顶点数V与图的密度ω之差，即S≤ω/2且S≤V－ω。
已知可嵌入平面中的最大完全图是K4，其顶点数V＝4，且可嵌入平面中的图的密度有四种，即ω分别可以是1，2，3，4。在满足S≤ω/2且S≤4－ω的情况下，二者中较小者就是某密度下的不可同化道路的条数S：
当ω＝1和4时，只能取S＝0，即不存在不可同化道路，最小完全同态的顶点数α＝ω＋S＝ω＋0＝ω＜4；当ω＝2和3时，只能取S＝1，也即在这种情况下，最多也都只能有一条不可同化道路，其最小完全同态的顶点数α＝ω＋S＝ω＋1≤4；
因为图的色数就等于其最小完全同态的顶点数，各密度下的平面图的最小完全同态的顶点数都没有大于4，也就说明了平面图的色数是不会大于4的，这就是四色猜测。四色猜测是正确的。
（6）用图的色数不大于图的密度的1.5倍来证明
平面图的密度一共有四种，即ω分别是1，2，3，4。当ω＝1时，色数γ≤1.5取γ＝1＜4；当ω＝2时，γ≤3＜4；当ω＝3时，γ≤4.5取γ＝4≤4；当ω＝4时，γ≤6，这似乎存在色数大于4 的情况，但在密度为4 的平面图中，只要有一条不可同化道路时，图就不再是平面图了。证明如下：
在一个K4团外若有一条不可同化道路Pn，则图中一共有4＋n个顶点，K4团中有6条边，Pn道路中有n－1条边，Pn道路与K4团相邻的有n×（4－2）＋2条边，共计6＋n－1＋n×（4－2）＋2＝7＋3n条边；如果这个图是平面图时，其边数最多只应是3×（4＋n）－6＝3n＋6条，而这时图的实际边数却是7＋3n，却是大于3n＋6的，所以这个图已不再是平面图而是非平面图了。所以ω＝4的平面图的色数是恒等于4 的。
从以上结果看，各个密度的平面图的色数都是没有大于4的，这也就证明了四色猜测是正确的。
（7）从对平面图的结构分析来进行证明
从平面图的结构上分析，单个图有独立顶点（K1图），有树，有圈，有轮，复杂一点的是由这些单图共同构成的图。一个连通图若只是一个独立顶点时，其色数一定是1；一个连通图是一棵树时，其色数一定是2；单个图是圈时，偶圈的色数是2，奇圈的色数是3，因为奇圈中一定有一条不可同化道路；单个图是轮时，偶轮（奇价轮）的色数是3，奇轮（偶价轮）的色数是4，同样也是因为奇轮中也一定有一条不可同化道路；若是含有以上各种单图构成的复杂图时，则含有奇轮（偶价轮）的图的色数是一定是4，否则，只含偶轮（奇价轮）或者只含奇圈的图的色数则是3，再否则，只含偶圈的图的色数则是2；不含圈和轮的树的色数总是2，独立顶点的色数也总是1。以上这些已包括了所有的平面图，其色数都没有大于4 ，所以有任何平面图的色数都是不大于4 的结论。这就是四色猜测。猜测正确。
（8）从地图的角度来证明四色猜测
设在某亏格为n的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色地图。那么这个“国数最小的”地图中也就应有γ个“国家”（这个“国数最小的”地图中的“国家”数γ，实际上就相当于图的最小完全同态的顶点数）。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与别的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域的总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这f（f－1）条边界线中每条边界线都是计算了两次的，则这个地图中的“边界线”的总条数即边数应是e＝f（f－1）/2。又因为地图是一个3—正则图，即每一个顶点都连着3条边，即所谓的“三界点”，所以该地图的总边数也可以写成e＝3v/2，从而有3v＝2e＝f（f－1）的关系。用区域数（即面数）f来表示顶点数v和边数e，则有v＝f（f－1）/3和e＝f（f－1）/2。把v＝f（f－1）/3和e＝f（f－1）/2代入到多阶曲面上图的欧拉公式v＋f－e＝2－2n则得到
f2－7f＋12（1－n）＝0
解这个关于“国数最小的”地图的区域数f的一元二次方程得正根是
        f＝（7＋√（1＋48n））/2
因为区域数必须是整数，所以上式还得向下取整，得
        f＝＜（7＋√（1＋48n））/2＞
式中用＜ ＞表示其中的数字向下取整。又因为f是两两均相邻的“国数最小的”地图的“国数”， 即区域数，所以这个“国数最小的”地
图染色时也必须用与其区域数相同的颜色数，所以又有
        γ＝f＝＜（7＋√（1＋48n））/2＞
这就是赫渥特的地图着色公式的“等式部分”。
从以上的讨论看，这个区域数f只是某一亏格为n的曲面上“国数最小的”地图中的“国数”最大者。若从这个“国数最小的”地图中去掉一条边，或者去掉一个“三界点”顶点及其所连的3条边，该地图中的区域数就都会减少。这个“国数最小的”地图原来是一个区域染一种颜色，那么现在区域数少了，所用的颜色数也就会减少下来。所以上式还可以再增添上“不等式部分”，即
        γ＝f≤＜（7＋√（1＋48n））/2＞
这就是赫渥特地图着色公式的全貌了，其中既有等式又有不等式。
式中当曲面的亏格为n＝0时，其色数γ＝f≤4，这就是地图中两两均相邻的区划数，也是就是地图四色猜测。这也就证明了四色猜测是正确的。地图的对偶图是一个极大图，地图的四色猜测是正确的，极大图的四色猜测也就是正确的。由极大图经过去点或去边后得到的任意平面图对于极大图来说，色数只会减少而不会增加，所以任意图的色数也是不会大于4 的，平面图的四色猜测也是正确的。
（9）用平面图欧拉公式直接求地图的染色数
设在亏格为0的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色地图。那么这个“国数最小的”地图中也就应有γ个“国家”。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与别的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域的总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这f（f－1）条边界线中每条边界线都是计算了两次的，则这个地图中的“边界线”的总条数即边数应是e＝f（f－1）/2。又因为地图是一个3—正则图，即每一个顶点都连着3条边，即所谓的“三界点”，所以该地图的总边数也可以写成e＝3v/2，从而有3v＝2e＝f（f－1）的关系。用区域数（即面数）f来表示顶点数v和边数e，则有v＝f（f－1）/3和e＝f（f－1）/2。
如果直接把v＝f（f－1）/3和e＝f（f－1）/2代入到亏格为n＝0的平面图的欧拉公式v＋f－e＝2中，就可以得到
f2－7f＋12＝0
解这个关于f的一元二次方程得两正根分别是
        f＝4和f＝3
这里取大值f＝4。这里也只有等式部分。因为两两均相邻的4 个区域染色时必须用四种颜色，所以也有γ＝f＝4。
这里的f＝4就是平面或球面上色数小于等于4的两两均相邻的“国数最小的”地图中的“国数”最大者，这个地图染色时必须用与其区域数相同数目的颜色。若从这个“国数最小的”地图中去掉一条边，或者去掉一个“三界点”顶点及其所连的3条边，该地图中的区域数就都会减少。这个“国数最小的”地图原来是一个区域染一种颜色，那么现在区域数少了，所用的颜色数也就会减少下来。所以上式还可以再增加“不等式部分”，即
    γ＝f≤4
这就是地图四色猜测。这也就证明了地图四色猜测是正确的。同样也就证明了平面图的四色猜测也是正确的。
（10）用哈德维格尔猜想证明四色猜测
根据哈德维格尔猜想（1943年，后被证明是正确的），“若图G是n色的，则G可以收缩为一个完全图Kn。”这里的“收缩”一词与我所用的“同化”一词是同一个概念，都是把两个不相邻的顶点凝结在一起的过程。
一个图只要其中含有K5团作其分子图，该图一定不是平面图，那么这样的图同化的最后结果一定是一个顶点数大于等于5的完全图；反过来，不含K5团作其分子图的图，却不一定都是平面图，如K3，3图。但可以肯定，平面图中是一定不含K5团作其分子图的。虽然不含K5团作其分子图的图同化时不一定都会得到顶点数小于5的完全图（如含 有不可同化道路的密度是4的图的最小完全同态的顶点数就是大于等于5 的），但至少可以肯定不含K5团作其分子图的平面图在同化时，是可以得到顶点数不大于4的完全图的，且这些完全图也都是平面图。
既然平面图同化的最终结果不会得到顶点数大于等于5的完全图，那么平面图同化的最终结果就一定只能是顶点数小于等于4的完全图了，这样的完全图在着色时，最多4种颜色也就够用了。这也就证明了四色猜测是正确的。
（未完见下一贴）
雷  明
二○一五年五月二十四日于长安

注：此文已于二○一五年五月二十五日在《中国博士网》上发表过，网址是：

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，