2—边连通3—正则平面图的可4—面着色——即地图四色猜测的证明

雷明85639720

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

1878年泰特曾猜想：2—边连通3—正则平面图（即地图）的可4—面着色与2—边连通3—正则平面图的可3—边着色是等价的。即只要证明了2—边连通3—正则平面图是可3—边着色的，就可以说明2—边连通3—正则平面图也是可4—面着色的，也就证明了地图四色猜测是正确的。是不是这样，我们只有通过证明才能辨别该猜想是否正确。
1、我在前两天的《2—边连通3—正则平面图的可3—边着色》和《任意2—边连通3—正则平面图的顶点数都是偶数》两篇论文中，已经证明了2—边连通3—正则平面图是可3—边着色的和任意2—边连通3—正则平面图的顶点数都是偶数是正确的。现在可以利用这两个结论对2—边连通3—正则平面图的可4—面着色与2—边连通3—正则平面图的可3—边着色是否等价进行证明。
2、我们已经证明了2—边连通3—正则平面图的顶点数v不但是偶数，而且其边数e还是顶点数v的1.5倍，即有e＝1.5v关系。由于2—边连通3—正则平面图的每个顶点均连着3条边，每条边就得用一种颜色，共用3种，且3种颜色所用次数相同，即都是1.5v/3＝0.5v次（1.5v是色边的总数，即边数），由于v是偶数，则每种颜色的使用次数0.5v一定是整数，不会出现小数的情况，符合实际。把分别用1、2、3三种颜色着色的边的集合用A1，A2，A3表示。
3、由于2中已得出每种颜色所用次数是0.5v次，即每种颜色的边只有0.5v条，那么由任两种颜色构成的边2—色链的总边数则是2×0.5v＝v，等于图的顶点数。说明了图中由任两种颜色构成的边2—色链的边数与图的顶点数是相等的，那么，每一种边2—色链，无论有几条，各条都一定是回路（即圈），各回路的顶点和边数也是相等的。这也说明了任两种颜色构成的所有边2—色回路中，已包含了图中所有的顶点，而不在该边2—色回路上的边都是着第三种颜色的边。这样以来任两种颜色构成的边2—色回路都把图分成了两部分——边2—色回路的内部和边2—色链的外部。
4、我们把某种边2—色回路的内部和外部两部分分别着上不同的颜色，则处在该边2—色回路内、外的各面均都成某一种颜色；再把另外一种不同的边2—色回路的内、外，也分别着以不同与前一种边2—色回路内、外所着的颜色；把这样的两种在边2—色回路内、外着好不同颜色的边2—色回路叠加起来，便会得到原来的2—边连通的3—正则平面图，颜色的叠加又会产生四种新的颜色，使得原2—边连通的3—正则平面图的相邻的各面具有不同的颜色，且图中只有四种颜色。这就可以得到任意2—边连通3—正则平面图是可4—面以的结论。当然也可以给两个边2—色回路的内，外着同样的两种颜色。但叠加时要认识到两种不同颜色，叠加的先后次序不同，所产生的新颜色是不同的。即ab与ba是不同的。
5、图1，a是我随便画一个2—边连通3—正则平面图（即地图，该图画成左右对称的了，好看一点。其实不对称也是可以的），然后再对其进行3—边着色（如图1，b）。


由色边集合A1和A2构成的子图是G1，2是一些没有公共顶点的1—2—1边2—色回路构成的（如图2，a）, 由色边集合A1和A3构成的子图是G1，3是一些没有公共顶点的1—3—1边2—色回路构成的（如图2，b）, 由色边集合A2和A3构成的子图是G2，3是一些没有公共顶点的2—3—2边2—色回路构成的（如图2，c）（图中边2—色回路用实线，第三条边用虚线）。
6、给图2，a中的1—2—1边2—色回路内、外各面分别着以a色和b色（如图3，a），给图2，b中的1—3—1边2—色回路内、外各面分别着以c色和d色（如图3，b）。


然后把图3，a中的边2—色回路子图G1，2和图3，b中的边2—色回路子图G1，3叠加到一起。因为每条边2—色回路中都含有3—正则图的所有顶点，两个边2—色回路又包含了3—正则图的所有的边，所以两个边2—色回路叠加到一起后，就得到了原来的2—边连通3—正则平面图（地图）。同时由于颜色的叠加，也新产生了ac，bc，ad，bd四种颜色，分别着在原图的各个面内（如图4，a），两相邻的面没有用相同颜色的。如果令ac，bc，ad，bd分别是A，B，C，D四种颜色，则如图4，b。


7、若给图2，a中的1—2—1边2—色回路内、外各面分别着以a色和b色（如图5，a），给图2，b中的1—3—1边2—色回路内、外各面同样分别着以a色和b色（如图5，b）。
然后把图5中的两个边2—色回路子图叠加到一起，也得到了原3—正则的平面图，也新产生了aa，ab，ba,bb四种颜色，并分别着在原图的各个面内（如图6，a），两相邻的面也没有用相同颜色的。如果令aa，ab，ba,bb分别是A，B，C，D四种颜色，则如图6，b。


8、若给图2，a中的1—2—1边2—色回路内、外各面分别着以a色（1色）和b色（2色）（如图7，a），给图2，b中的1—3—1边2—色回路内、外各面同样分别着以a色（1色）和c色（3色），即分别使用与其边2—色回路对应相同的颜色（如图7，b）。
然后把图7中的两个边2—色回路子图叠加到一起，也得到了原3—正则的平面图，也新产生了aa，ab，ac,bc四种颜色，并分别着在原图的各个面内（如图8，a），两相邻的面也没有用相同颜色的。如果令aa，ab，ac,bc分别是A，B，C，D四种颜色，则如图8，b。
9、如果令A，B，C，D分别代表的是红色，兰色，绿色和黄色，则图4，b，图6，b和图8，b三个4—面着色模式则分别如图9，a，图9，b和图9，c所示。

10、同样的，如果我们把1—2—1边2—色回路G1，2与2—3—2边2—色回路G2，3叠加到一起，或把1—3—1边2—色回路G1，3与2—3—2边2—色回路G2，3叠加到一起，都可以得到用四种颜色着色的2—边连通3—正则平面图（地图）的另外的4—着色模式。
到此，就证明了2—边连通的3—正则平面图（地图）的3—边着色就等价于2—边连通的3—正则图平面图（地图）的4—面着色，地图四色猜测也就得到了证明是正确的。
11、泰特猜测是正确的。以上的证明，说明了任何2—边连通的3—正则平面图（地图）的可3—边着色与2—边连通的3—正则平面图（地图）的可4—面着色是等价的。即只要证明了任何2—边连通的3—正则平面图（地图）是可3—边着色的，就等于证明了任何2—边连通的3—正则平面图（地图）是可4—面着色的，1852年法朗西斯提出的地图四色猜测是正确的。
12、平面图四色猜测的证明。这里所说的平面图的四色猜测是指对平面图的顶点的着色。平面图的四色猜测是：任何平面图的（顶点）着色数都不大于4。给地图（2—连通的3—正则平面图）的面着色，就是给其对偶图的顶点着色。地图是可4—面着色的，也就说明了其对偶图是可4—顶点着色的。而任何2—边连通的3—正则平面图（地图）的对偶图都是极大的平面图，所有的面都是三角形面，是相同顶点数的平面图中边数最多，面数最多的图。由极大图通过“去点”或“减边”后所得到的图不但仍是平面图，而且其色数是只会减少而不会再增加。因此，这也就证明了任意平面图的色数都是不会大于4的，平面图的四色猜测也是正确的。
12、附说明：本文中所用的任两条边2—色回路叠加到一起的办法，可以得到原来的3—正则图，这是没有问题的；但对每一条边2—色回路内、外着以不同的两种颜色，两条边2—色回路中共四种颜色，得到新的四种颜色的原理可否用画家配色的原理来解释，如图8。颜色叠加我也是爱了画画配色的启发而产生的。


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

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

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

谢谢了。

雷明85639720

，，，，