无割边的3—正则平面图可3—边着色的证明

雷明85639720

无割边的3—正则平面图可3—边着色的证明
雷  明
（二○一七年三月十七日）

无割边的3—正则图就是地图的原型，每个顶点的度都是3，即地图中的“三界点”。由于有泰特猜想：2—连通的3—正则平面图的3边着色等价于其可4—面着色。所以只要证明了任何无割边的3—正则平面图都是可3—边着色的，就可以说证明了地图四色猜测是正确的。
首先由于3—正则图的每一个顶点都连着3条边，那么该类图的总度数就是3v（v是图的顶点数），又因为一条边是两度，所以该类图的边数是e＝3v／2＝1.5v，即边数是顶点数的1.5倍。可以看出，只有当顶点数v是偶数时，才能保证这类图的边数是整数，所以又有这类图的顶点数一定是偶数的结论。
    1、第一种证明方法
因为3—正则图的顶点数一定是偶数，所以该图的顶点一定可以划分为若干个（包括一个）偶数个顶点的集团，由于该图是连通的，所以每个偶数个顶点的集团一定会构成一个偶圈。这些圈的分布可以是大圈套小圈式的，也可以是并列式的，也可以是二者兼有的。给这些偶圈进行边着色时，两种颜色交替的着色，两种颜色就够用了。剩下来的那些边（相当于顶点数的一半）的两端均与这些偶圈中的某一个已着有1色和2色的两个顶点相邻，给这些边都着以第3种颜色完全是可以的。所以无割边的3—正则平面图边着色时是不会用到第四种颜色的。这就证明了无割边的3—正则平面图一定是可3—边着色的。如图1的无割边的3—正则平面图，就是一个可3—边着色的图。而图1，c则是一个有割边的3—正则平面图，它的边色数是4而不是3。



2、第二种证明方法



2、1  因为图的边着色就是对其对边图（即线图，线图即把原图的边作为新的顶点，并按原图中边与边的相邻关系作新边所得到的图）的顶点着色，而3—正则图的边图又是一个密度（即最大团的顶点数）是3的平面图（如图2中加粗的边和加大的顶点所构成的图），并且是一个4—正则的平面图（因为原3—正则图中每一条边的两端总共均连着4条边，所以就有其边图中每个顶点均连有四个顶点）。但这个4—正则平面图只是从对无割边的3—正则平面图作线图而得到的4—正则平面图，并不是指任何的4—正则图。
2、2  由于无割边的3—正则平面图的边图的最大团是一个K3团，其顶点数就是该图的密度，所以该图着色时最少也要用三种颜色；又由于该图中最大的轮是4—轮，所以其色数最大也只能是3；还由于该边图中还有边数大于3的多边形面，即边数大于3的圈，而圈的着数最多也只要三种颜色就够了。所以，这就能够决定该图的色数是3而不会是4。



2、3  通过画图，还可以看出，除了正4—面体（即K4图）这个3—正则平面图中每个面都是三角形面，其线图中的每一个顶点都处在一个4—轮的中心顶点（如图3，该图的色数是3）外，其他的3—正则平面图中，至少都会含有一个面的边数是大于等于4的。这样的3—正则图的线图中，至少会有一个面的边数大于等于4的多边形（如图4）。处在这种多边形上顶点上的、属于图中的顶点，其度仍一定是4（因为该边图本来就是一个4—正则的平面图），是不可能位于一个大于4轮的中心顶点位置的，这个边数大于等于4的多边形面也是不可能与别的顶点构成轮沿顶点数大于等于4的轮的，特别是不可能构成轮沿顶点数大于等于3的奇轮。这也就决定了该边图的色数只能是3而不会是4。
2、4  因此可知，无割边的3—正则平面图的边色数都是3，他们都是可以3—边着色的。图5到图8分别是图1，a的无割边的3—正则平面图和图1，c的有割边的3—正则平面图的边着色例图。
3、四色猜测是正确的
通过以上的证明，说明了任何无割边的3—正则平面图都是可3—边着色的。根据泰猜想（或定理）可知，无割边的3—正则平面图的可3—边着色等价于其可4—面着色，可知地图的四色猜测是正确的。地图四色猜测是正确的，对其对偶图——极大平面图——的顶点着色色数也是不会大于4的。由极大平面图通过去顶或减边所得到的任意平面图的顶点着色色数只会减少而不会增大，所以也就有任意平面图的色数也是不会大于4的。这就证明了四色猜测是正确的。








   

雷  明
二○一七年三月十七日于长安

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

雷明85639720

，，，，