塔特图的各种着色和2—连通3—正则平面图是可3—边着色的证明

雷明85639720

塔特图的各种着色和2—连通3—正则平面图是可3—边着色的证明
雷  明
（二○一五年五月二十七日）

最近我与网名“夜泊秦淮”的网友在讨论塔特图是否可3—边着色的问题，通过着色，确实证明了这个不可哈密顿（图中无哈密顿圈）的3—正则平面图是可3—边着色的。进一步说明了只要是无桥的3—正则的平面图，不管其是否可哈密顿，即不管图中有无哈密顿圈，都是可3—边着色的（后面我们还要进一步进行让明）。现在我把塔特图的各种着色（边着色，线图的着色，顶点着色，面着色和对偶图的着色）分别叙述如后。
1、塔特图的3—边着色：
塔特图如图1。
从顶点①开始找一条哈密顿道路，经过所有的顶点，最后到达顶点②，如图2，图中加粗加黑了的边就是一条哈密顿道路。从顶点①开始对该哈密顿道路上的各边用1和2两种颜色着色，直到顶点②为止；再把该哈密顿道路以外未着色的边用颜色3着上，如图2。现在只剩下边①和边②未着上1，2，3三种颜色之一，似乎只能着第四种颜色。可是我们发现，若把从顶点③到顶点④的边二色链2—3进行坎泊创造的颜色交换后，给边①和边②均可着上颜色2，如图3。图中只用了三种颜色。因此，塔特图是可3—边着色的。


    2、塔特图的线图的顶点着色：
图的边着色实际上就是对图的线图的顶点着色。塔特图的线图如图4所示，它是一个密度是3（图中最大团是K3，其顶点数是3）的4—正则图。
我们仍从顶点①开始着起，同样到最后顶点②和顶点③也似乎只能着第四种颜色，但对顶点④到顶点⑤的2—3色链进行坎泊交换后，可空出颜色2来，分别给顶点②和顶点③着上，如图5。图中也没有出现第四种颜色。塔特图是可3—边着色的。


3、塔特图的顶点着色：
塔特图的顶点着色如图6。从图中可见其色数是3。也是一个3—色图。为什么是3色的，因为图中有5—圈，5—圈着色必需要用三种颜色，所以其色数是3；另外根据我的同化理论，图的色数是大于等于图的密度，而又小于等于图的密度的一倍半，塔特图的密度是2（图中最大团是K2，其顶点数是2），其色数最大是不会大于1.5×2＝3的。


4、塔特图的面着色：
在对塔特图进行面着色时，为了方便先对塔特图的对偶图进行顶点着色，然后再对原塔特图进行面着色。塔特图的对偶图的顶点着色如图7，塔特图的面着色如图8。塔特图对偶图中的顶点就是原塔特图中的面，图中只标出了部分的对应关系。两图都均用了四种颜色。


5、2—连通3—正则平面图可3—边着色的证明：
当年泰特证明2—连通3—正则平面图是3—边着色时，认为所有的3—正则图均是可哈密顿的，把哈密顿圈上的边用两种颜色交替的进行着色。由于每个3—正则图都有偶数个顶点，当然也就有偶数条边，所以哈密顿圈上的边一共用了两种颜色。把其余的没有在哈密顿圈上的边均着上第三种颜色，该3—正则平面图的3—边着色就可完成。
可我们对塔特图的边着色却说明，非哈密顿的3—正则平面图也是可3—边着色的。这就进一步证明了三个问题：第一，并不是所有的3—正则平面图都是可哈密顿的；第二，也并不只是可哈密顿的3—正则平面图才是可3—边着色的；第三，只要是3—正则的平面图（地图）都是可3—边着色的。
为什么3—正则的平面图的边着色数是3呢。因为图的边着色就是对其线图的顶点着色。而3—正则平面图的线图的密度是3（原图中的顶点度是3，在线图中则表现出的是一个三角形面，即K3团，有3个顶点，所以密度是3），且是4—正则的（3—正则平面图中的每条边均连接着两个面的两条边，在其线图中就表现为每个顶点的度均是4），图中只有圈，而没有轮。由于其密度是3，就决定了该图着色时一定要用三种颜色，再由于图中只有圈而没有轮，也就不存在奇轮着色时其中心顶点需要第四种颜色的情况。所以3—正则平面图的线图着色一定需要三种颜色，不会多也不会少。这就证明了3—正则平面图的边着色的色数一定是3。
6、3—正则图的顶点一定是偶数的证明：
3—正则图的总度数是3v，边数是e＝3v/2，由于图的边数必须是整数，所以总度数3v也必须是偶数时才能被2整除，而要保证3v是整数， 顶点数v也必须是偶数才能满足，因为3只有乘以偶数时也才能使所得到的积是偶数。这就证明了任何3—正则图的顶点数一定是偶数，当然3—正则的平面图也不能例外。


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

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

雷明85639720

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