2—连通3—正则平面图的可3—边着色的证明

雷明85639720

2—连通3—正则平面图的可3—边着色的证明
雷  明
（二○一六年十月十五日）

1878年泰特给出了一个猜想，把3—正则平面图（地图）的面着色与其边着色联系了起来。泰特猜想说：3—正则平面图（地图）是可4—面着色的，当且仅当它是3—边着色的。也就是说，（地图）四色猜测成立，当且仅当3—正则平面图是3—边可着色的。
我们虽然看不出3—正则平面图的面着色与其边着色的关系，更看不出该图的4—面着色与其3—边着色的关系，但是我们可以证明每一个3—正则的平面图都是可3—边着色的。
1、3—正则平面图（地图）的3—边着色：
图的边着色就是对其线图（即边图）的顶点着色。线图就是把原图中的边作为新的顶点，又保持原图中边与边的相邻关系，所作的新图，3—正则平面图的线图如图1所示（图中的小黑点和细线是原3—正则平面图的顶点和边，而大黑点和粗线则是原图的线图的顶点和边）。3—正则平面图的线图的密度（即线图中的最大团的顶点数），就是原图（在这里的原图就是指3—正则的平面图）的最大度3（3—正则图的每个顶点的度都是3），所以其线图的密度就是3，即3—正则平面图的线图中的最大团是K3；由于原图中每一条边的两端所连的边总共都是4条，所以线图中的每一个顶点则均连着4条边，即线图又是一个4—正则图。通过画图，可以看出除了K4这个3—正则平面图的线图中的每一个顶点都处在一个4—轮的中心顶点（如图2的正四面体图中的各顶点）外，其他的3—正则平面图的线图中，与每一个顶点相邻的四个面中，至少有一个面是边数大于3的多边形，所以每个顶点都不是处在一个轮的中心顶点上（如图3、4、5中的各顶点）。

设原3—正则平面图中的顶点数、边数、面数分别是v、f、e，其线图中的顶点数就是原图的边数，有v线＝e，原图中与每一个顶点（如图1中原图的顶点A、B、C、D等）所连的3条边在线图中构成的是一个三角形面（如图1中线图的面A、面B、面C、面D等），原图中的每一个面的各边所对应的新顶点及其之间的边，在线图中又构成了一个与原面边数相同的面（如图1中标示的线图中的三边形面、四边形面、五边形面等也相应是原图中的同边数面），所以线图的面数f线＝v＋f，又因为线图是4—正则的，所以其边数e线＝（4×v线）＝4e/2＝2e。
把3—正则平面图的线图的v线＝e，f线＝v＋f，e线＝2e代入平面图的欧拉公式，得左边＝v线＋f线＝e＋v＋f，右边＝e线＋2＝2e＋2＝e＋e＋2，相当于公式左右两边分别都同时加了一个e，实际上左右两边还相等的。所以，这也就证明了3—正则平面图的线图仍是平面图。
由于3—正则平面图的线图是密度为3的平面图，所以其色数是决不会小于其密度3的；又因为该线图中没有轮，当然也就不可能有奇轮了，也就不可能在最大团K3外有不可同化的道路了，其色数又不可能大于其密度3；所以说该线图的最小完全同态只能是K3，该完全同态的顶点数是3；又因为图的色数等于其最小完全同态的顶点数，所以该线图的色数一定是等于3的。这就证明了3—正则平面图的线色数是3，即3—正则平面图是可3—边着色的。
2、举例：用几个3—正则平面图对1中的结论进行检验。
①　正四面体：正四面体对应的图及其线图的3—边着色如图2所示。图中只用了●、○、★三种颜色；

正四面体的v＝4，f＝4，e＝6；其线图的v线＝e＝6，f线＝v＋f＝4＋4＝8，e线＝2e＝12；把v线、f线、e线代入平面图欧拉公式中，左边＝v线＋f线＝6＋8＝14，右边＝e线＋2＝12＋2＝14，两边相等。
②　正六面体：正六面体对应的图及其线图的3—边着色如图3所示。图中也只用了●、○、★三种颜色；
正六面体的v＝8，f＝6，e＝12；其线图的v线＝e＝12，f线＝v＋f＝8＋6＝14，e线＝2e＝24；把v线、f线、e线代入平面图欧拉公式中，左边＝v线＋f线＝12＋14＝26，右边＝e线＋2＝24＋2＝26，两边相等。

③　正十二面体：正十二面体对应的图及其线图的3—边着色如图4所示。图中也只用了●、○、★三种颜色；

正十二面体的v＝20，f＝12，e＝30；其线图的v线＝e＝30，f线＝v＋f＝20＋12＝32，e线＝2e＝60；把v线、f线、e线代入平面图欧拉公式中，左边＝v线＋f线＝30＋32＝62，右边＝e线＋2＝60＋2＝62，两边相等。
④　六棱柱：六棱柱对应的图及其线图的3—边着色如图5所示。图中仍是也只用了●、○、★三种颜色；
通过对以上几个3—正则平面图的边着色实践，可以看出任何3—正则的平面图，的确是可3—边着色的。3—正则平面图是可3—边着色的结论是正确的。

3、泰特猜想是否成立？
泰特猜想是任何3—正则的平面图（地图）的可4—面着色等阶于3—正则平面图的可3—边着色。上面我们已经证明了任何3—正则平面图都是可3—边着色的，但这种图的可3—边着色，与其是否可4—面着色有什么关系，怎么样去证明，我们还是不能证明的。它不象3—正则平面图（地图）的面着色与其对偶图——极大图——的顶点着色等价那样，是在两类不同的图间进行的研究和比较，而是在同类图或同一个图间进行的。所以我认为这个猜想似乎是不可能成立的。但又找不出充分的理由对其进行否定。所以本人在这里向高手请教，那位大人物或爱好者能对其进行一下证明或说明。本人表示衷心的感谢。



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

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

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，