任何地图都是可3—边着色的——四色猜测证明方法之二

雷明85639720

任何地图都是可3—边着色的
——四色猜测证明方法之二
雷  明
（二○一六年十二月二十九日）

1、泰特猜想的证明：
地图本身就是一个2—边连通的3—正则平面图。泰特曾经猜测想：2—边连通的3—正则平面图的可4—面着色（即地图四色猜测）等价于3—正则平面图的可3—边着色。这个猜想也是不难证明的。
3—正则平面图的特征——顶点数是偶数，边数是顶点数的1.5倍以及其是可3—边着色的，且三种颜色的边的数量也是相同的——同样也适用于地图。① 地图中的总度数是3v（v是地图中的“三界点”顶点数），每条边的两端各是1度，地图中e条边的总度数则是2e，即有3v＝2e的关系。这个公式不但说明了地图的边数是顶点数的1.5倍（即e＝3v/2＝1.5 v）；② 同时又说明了地图的顶点数一定是偶数，因为只有v是偶数时才能使边数e是整数，所以地图的顶点数一定是偶数。③ 地图的边数是e＝1.5 v，那么图中着色的边也就是1.5 v，每个顶点都连结着3种颜色的边，所以1.5 v/3＝0.5v，即着每种颜色的边都是0.5v条，三种颜色的边的条数是相等的。
若一个2—边连通的3—正则平面图是可3—边着色的，由于每个顶点都连结着三种颜色的边，则其任一种边2—色子图（若干条回路）一定是包含了图的所有顶点，该子图中的边和顶点不但相等而且都是偶数，剩下的该子图以外的相当于图的顶点数的一半数量的偶数条边，全是着第三种颜色的边。把某一种边2—色子图回路的两侧各个着以不同的颜色，则两种不同的边2—色子图叠加后，就可得到原来2—边连通的3—正则平面图。两种边2—色子图回路两侧的四种颜色叠加的结果，就象画家配制颜料一样，产生了四种新的颜色，分别着在原图中的各个面内，且两相邻的面具有不同的颜色。这就证明了泰特的猜想是正确的。同时，地图的可3—边着色等价于其可4—面着色也是正确的。



举一个简单的例子，正六面体图这个3—正则图的地图如图1。该图是可3—边着色的，也是可4—面着色的。最后着色只有三种颜色，是因为1—2—1边2—色子图中的a色没有与1—3—1边2—色子图中的b色相叠加，不可能产生第四种颜色，所以最后只用了三种颜色。
可以看出，欲证地图四色猜测是否正确，只要证明2—边连通3—正则平面图是否可以3—边着色的就可以了。
2、2—边连通3—正则平面图是可3—边着色的
① 3—正则平面图中的每个顶点都边有3条边，相关联的边不能用同一种颜色，所以其在边着色时，至少也要用三种颜色；② 又因为3—正则平面图中面的边数是任意的，所以若有一个面的边数是奇数时，该面的边着色最多也只要三种颜色也就够用了；③ 所以说3—正则的平面图是可3—边着色的。
3—正则平面图的可3—边着色，还可以这样来证明：① 由于图的边着色就是对其线图的顶点着色，而3—正则平面图的每个顶点（如图2，a中的a和b两顶点）所连结的3条边，在其线图中就都构成了一个3边形的面，是一个K3团，所以这个线图的密度就是3；② 又是由于3—正则平面图的每条边的两个端点顶点（如图2，a中的边a—b的端点a和b）共连结着4条边，在其线图中就表现为每个顶点均连结有4条边和4个顶点（如图2，a中的顶点0连结着1、2、3、4四个顶点），所以线3—正则平面图的线图是一个4—正则图。如图2，a。

① 因为3—正则平面图的线图的密度是3，所以其着色时至少就需要3种颜色；② 又由于该线图是4—正则的，每个顶点都连结着4个顶点，而以线图中每个顶点为中心时，最大只可能得到一个4—轮（如图2中的顶点1和2，3和4间均相邻时，比如正4—面体的线图（如图2，c）就是这样），4—轮着色只用3种颜色；③ 由于线图中的每个顶点又不可能处在一个完整的奇轮的中心（如图2，a中的顶点1和2，3和4间至少有一对不相邻时），所以该残轮着色时最多也不会超过3种颜色（奇轮的色数是4）；④ 综合以上的三种原因，可知该线图的色数一定是3，这也就证明了3—正则平面图是可3—边着色的结论是正确的。同时也就证明了任何地图都是可4—面着色的结论也是正确的，即地图四色猜测是正确的。
由于地图的每个顶点均连结着3种颜色的边，三种颜色的边数又都相同，都是顶点数的一半；所以图中由某两种颜色构成的边2—色子图一定包括了地图中的所有的顶点，并包括了图中三分之二的边数，剩余的三分之一的边就是着第三种颜色的边；第三种颜色的边的两个端点顶点都是上述边2—色子图中的顶点。
3、平面图的四色猜测也是正确的
因为2—边连通3—正则图（地图）是可4—面着色的，那么地图的对偶图——极大图——也就是可4—（顶点）着色的。而由任意的极大图经过减边或者去顶的办法，得到的任意平面图的色数只会是减少，而不可能再增大。所以也就证明了任意平面图也都是可4—（顶点）着色的，平面图的四色猜测也就得到了证明是正确的。
4、赫渥特地图的4—着色
图3到图7是赫渥特地图4—着色的各个步骤。图7是赫渥特地图可4—面着色的彩色地图。从赫渥特的可3—边着色，到它的可4—面着色，进一步验证了2—边连通3—正则平面图既是可3—边着色的，又是可4—面着色的。







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

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

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，