用动态极大图着色法证明四色猜测

雷明85639720

用动态极大图着色法证明四色猜测
雷  明
（二○二二年二月十九日）

1、任何地图（无割边的3—正则平面图）的对偶图都是一个极大平面图。对极大平面图的顶点着色就相当于给地图的面的染色。只要任何极大平面图着色时四种颜色够用了，那么任何地图染色时四种颜色也就够用了，地图的四色猜测就是正确的。由于平面极大图经过“去顶”和“减边”运算后所得到的任意平面图的色数只会比极大平面图的色数减少，而不会再增大，所以任意平面图着色时，四种颜色也就够用了。平面图的四色猜测也就是正确的了。

2、由于极大平面图的各个面均是三边形面，所以在极大平面图的任何一个面内增加一个顶点时，最多只可能与三个顶点相邻（如图1。该顶点是处在一个3—轮的中心，相当于地图中的“三国环国”），同时也增加了三条边和两个三边形面。在极大平面图的任何一条边上增加一个顶点时，最少也得要与两个顶点相邻（如图2。该顶点是处在一个2—轮的中心，相当于地图中的“两国夹国”），也可与三个顶点相邻（如图3。该顶点是处在一个3—轮的中心，也相当于地图中的“三国环国”），但最多只可能与四个顶点相邻（如图4。该顶点是处在一个4—轮的中心，相当于地图中的“四国环国”）。只要是增加了一个顶点，也都是增加了三条边和两个三边形面。当然还有一种特殊的情况，即在极大平面图的一个面内增加一个顶点，而只与一个顶点相邻时（如图5。该顶点是处在一个1—轮的中心，相当于地图中的“国中之国”，只与一个“国家”相邻，但这时的图就不再是极大平面图了）。也是由于极大平面图的各个面都是三边形面的原因，所以无论是在极大平面图的面内，还是在极大平面图的边上增加顶点时，也都不会产生与五个以上（含五个）顶点相邻的情况。

3、所谓动态极大图着色，就是从已着色的最小的极大平面图——完全图K2开始，一个一个的增加顶点，并对所增加的顶点一个一个的进行着色，并一直使图保证处在极大平面图的状态。最小的极大平面图中有三个顶点、三条边和两个面，着色时三种颜色就够用了。所以极大平面图的色数最小是3。然后再在这个已着有三种颜色的极大平面图内增加顶点，当与增加的顶点相邻的顶点数小于4时，该顶点一定是还有至少一种颜色可着的；当与增加的顶点相邻的顶点数等于4时（如图6）。按坎泊1879年所创造的颜色交换技术，该顶点也一定是可以着上图中已用过的四种颜色之一的。由于在极大平面图内增加顶点时，与其相邻的顶点数是绝不会大于4的，而该增加的顶点也一定可着上图中已用过的四种颜色之一，所以极大平面图着色时，四种颜色一定是够用了。
4、用以上的这种骤步增加顶点的办法从给一个最小的极大平面图中骤步的增加顶点，就可以得到任意的极大平面图，顶点数以至可以达到无穷。所增加的任何一个顶点所用的颜色都是不会超出四种颜色之外的。这就是在动态中（因为极大图的顶点是骤步增加的，以至无穷）从理论上证明了极大平面图的四色猜测是正确的。当然地图的四色猜测和平面图的四色猜测也就都得到证明是正确的。四色猜测可以上升为四色定理进行应用了。
5、但这只是理论上的证明，而我们平时遇到的实际问题则是给具体地图的着色，其对偶图是一个具体的极大平面图。要着色的对象是一个静态的，顶点数和边数都是不可再变动的具体的极大平面图。着色时是要在这个具体的极大平面图的基础上，一个顶点一个顶点的去着。不会象上述证明中所说的那样，从一个最小的极大平面图开始，一边着色，一边增加顶点，得到一个新的极大平面图，再对新的极大平面图中的新顶点进行着色，颜色数总是不会超过四种的。而在对具体极大平面图着色时，总是要有最后一个要着色的顶点的，若该顶点只与4个以下的顶点相邻，或这个顶点的相邻顶点只占用了三种颜色时，该顶点还是可以着上图中已用过的四种颜色之一的。但若与该顶点相邻的顶点数大于4，或者所占用的颜色数等于4时，该如何处理呢？这是一个具体的实际问题，还得要继续进行研究。本文只解决了极大平面图着色时，四种颜色就够用了的问题，即只解决了能够“怎么样”的问题。并没有解决如何对一个具体的极大平面图用四种颜色着色的问题，即如何去解决“怎么样”的问题。还得另文专门研究具体的极大平面图的着色方法问题。

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

注：此文已于二○二二年二月二十五日在《中国博士网》上发表过，网址是：
http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=5047

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，