从3—正则平面图的可3—边着色到四色猜测的证明

雷明85639720

从3—正则平面图的可3—边着色到四色猜测的证明
雷  明
（二○一五年六月九日）

地图本身就是一个3—正则平面图，只要证明了3—正则图是可4—面着色的，也就等于证明了地图四色猜测是正确的。
1、图同化的理论
图顶点着色的色数就是其最小完全同态的顶点数。图的完全同态是对图进行了一系列的同化后，所得到的一个顶点数不能再少的完全图。同化是把两个不相邻的顶点凝结在一起的过程。正确的同化方法是在两个有最短的距离的不相邻的顶点间进行，即同化的两个顶点中间只相隔一个顶点。
由于图中的最大团中的各顶点均是相邻的，不可能再进行同化，所以图的最小完全同态的顶点数一定是不小于图中最大团的顶点数的，即不小于图的密度的。图的密度就是图中最大团的顶点数。
通过对同化过程的研究可知，图的最小完全同态的顶点数是不大于图的密度的一倍半的。比如，奇圈和奇轮的密度分别是2和3，但其色数却是3和4，都不大于其密度的一倍半。
为什么图的最小完全同态的顶点数会大于图的密度呢。这是因为图中存在着同化不到最大团中去的顶点，而这种顶点的存在是由于图中存在着对于某一个最大团来说的不可同化道路。比如5—圈（奇圈）中的最大团是K2，密度是2，但同化的最后总是一个3—圈（K3图），有3个顶点。这是因为5—圈中的任一个最大团K2以外的其他顶点和边对该K2团都构成了一条不可同化道路。这条不可同化道路中的每一个顶点都有可能同化不到该最大团中去，所以5—圈以及其他顶点数大于等于5的奇圈的最小完全同态都是K3图。同理轮沿顶点数大于等于5的奇轮的最小完全同态一定是K4图也是这样产生的。
为什么图的色数的上界是图的密度的一倍半呢。这是因为图的密度的不同，各不可同化道路间可构成联的最大条数是不同的。若一个图的密度是ω，图中对某个最大团来说，有S条不可同化道路间构成了联，该联本身的密度是2S，而联只是图中的一个分子图，所以有2S≤ω，即有S≤ω/2。加上图中最大团的顶点数ω，图的色数的上界就是图的密度的一倍半。
这样，对于密度不大于4的任何平面图来说：密度是1的图的色数总是1；密度是2的图的色数只能是2或3；密度是3的图的色数只能是3或4；密度是4的图似乎其色数是有可能会大于4的，但可以证明，这种情况下的图已不再是平面图了，而是密度为4的非平面图（平面图的密度一定小于等于4，但密度小于等于4的图却不一定都是平面图，如K3，3图就是一个非平面图，其密度是2，是小于4的。）。所以密度为4的平面图的色数是恒等于4 的。
由于以上的原因，我们可以得出，含有轮沿顶点数大于等于5的奇轮的平面图的色数一定是4，否则，只要该平面图本身的密度不是4，其色数一定是不会大于3 的。
2、3—正则平面图（地图）是可3—边着色的证明
图的边着色就是对其线图的顶点着色。因为线图的密度等于原图的最大度，而3—正则平面图的最大度是3，所以3—正则图的线图的密度是3，其色数也决不会小于3；又因为线图的顶点就是原图的边，而3—正则平面图的每条边均是连接着4条边，所以3—正则平面图的线图是一个4—正则的平面图，并且图中最大只可能有4—轮，而没有任何奇轮，不可能存在不可同化道路，所以该图的色数一定也不会大于3。这就证明了3—正则平面图都是可3—边着色的。正好3—正则平面图的每个顶点均连有3种颜色的边。
3、地图四色猜测的证明
地图本身就是一个3—正则的平面图。证明了任何3—正则平面图是可4—面着色的，也就让明了地图的四色猜测是正确的。
一个可3—边着色的3—正则平面图的每一个顶点都是连接着分别用三种颜色着色的三条边，任两种颜色的边都构成了若干个边二色圈（环），并把全图分成了若干部分。现在用“颜色重叠法”来证明3—正则平面图也是可4—面着色的。所谓“颜色重叠法”就是把两种颜色重叠后所形成的一种新颜色。
我们先把被3—正则平面图中由1、2两种颜色构成的边二色圈所分成的各部分间隔的分别着以a，b两种颜色，然后再把图中被1、3（或2、3）两种颜色构成的边二色圈所分成的各部分间隔的分别着以c，d两种颜色。两种边二色圈的并就是图中所有的边，构成了整个3—正则平面图。两次染色颜色的重叠，共产生了ac、ad、bc、bd四种新的颜色。这时图中所有的面都染了这四种新颜色中某一种颜色，没有出现第五种颜色，且相邻面间具有不同的颜色。这就证明了地图的四色猜测是正确的。
这种证明方法，基本类似于韦斯特和徐俊杰的证明方法，但又有所不同。韦斯特的方法说得糊里糊涂，看不明白；徐俊杰的证明虽能看明白，但没有讲清两种边二色圈重叠就可以得到原3—正则平面图，且图中所有的面均已染上了由两种不同颜色重叠而得到的一种颜色。使读者容易发出为什么不把第三种边二色圈也重叠一次的凝问（其实这一重叠是多举一次的，因为两次重叠就已经得到原3—正则平面图了）。
4、平面图四色猜测的证明
平面图的面着色就是对其对偶图的顶点着色。既然任意的3—正则平面图（地图）都是可4—面着色的，那么它的对偶图也就是可4—（顶点）着色的。因为3—正则图的对偶图是一个极大图，所以极大图也是可4—着色的。把一个极大图通过减边或去顶，可以得到任意的平面图，这个任意的平面图的顶点着色色数只会比极大图的色数减少而不会增加，所以任意的平面图也一定是可4—着色的。这就证明了平面图的四色猜测也是正确的。
5、四色猜测是正确的
到此，已分别证明了地图的四色猜测和平面图的四色猜测都是正确的。所以说四色猜测是正确的。


雷  明
二○一五年六月九日于长安

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

雷明85639720

,,,,,,,,

雷明85639720

有网友11223344提出不一定所有的3—正则平面图都是可3—边着色的，所以我这个证明可能就是失败的。但对于可3—边着色的3—正则平面图来说，它则一定是可4—面着色的。但这并不代表所有的3—正则平面图（地图）都一定是也是可4—面着色的，所以猜测还是没有被证明是正确的。

雷明85639720

,,,,,,,,,,