待着色顶点移动法证明四色猜测

雷明85639720

待着色顶点移动法证明四色猜测
雷    明    刘千栋
（二〇二三年四月五日）

【摘  要】 四色猜测也叫四色问题。是专门研究关于对地图中区划的染色问题的。由于地图是属于图论中的“无割边的3—正则的平面图”，所以给地图的面（区划）上的染色也就是对地图的对偶图——极大平面图的顶点着色。极大平面图的四色问题解决了，不仅只是证明了地图四色猜测是正确的，同时还可说明任意平面图的四色猜测也是正确的。因为能够可4—着色的极大平面图，经去顶和减边后，所得到的任意平面图的色数只会减少而不会再增加。
【关键词】 四色猜测  四色问题  待着色顶点  构形  不可避免顶点    待着色顶点移动  着色  平面图  度
  
    1，待着色顶点与构形。在给任何平面图着色时，都一定要遇到最后一个要着色的顶点，这就是待着色顶点，用Ⅴ0表示。与V0相邻的顶点都叫做围栏顶点。把这样的只有一个顶点未着色的图就叫做构形。V0能否着上图中已用过的四种颜色之一，是解决四色问题的关键。想办法把V0着上四种颜色之一的过程，也就是证明四色猜测成立的过程。平面图中的任何一个顶点都可作待着色顶点。
    2，终局构形与困局构形。若围栏的顶点数（即待着色顶点Ⅴ0的度）为d，则有d≥0。又若围栏顶点所占用的颜色数为c，则有c≤4。
    ①终局构形。当d＜4或c＜4时的构形，就是终局构形。Ⅴ0是一定能够直接着上四种颜色之一的。这样的Ⅴ0就是终局顶点。
    ②困局构形。当d≥4和c＝4时的构形，则是困局构形。但其Ⅴ0却是暂时还不能着上四种颜色之一的。这样的困局必须经过待着色顶点的移动，把困局顶点Ⅴ0转化成终局顶点V0，才能着上四种颜色之一。
    3，待着色顶点移动。把困局围栏顶点中使用次数最少的一种颜色给V0着上，就在围栏中新产生了一个或多个新的待着色顶点，这就是待着色顶点的移动。重复以上的操作，可以把Ⅴ0移动到图中的任何一个顶点之上。待着色顶点移动的目的就是为了把困局顶点转化成终局顶点，再进行直接着色。
    4，不可避免顶点。任何平面图中都存在着至少一个顶点的度是小于等于5的，具有这几种度的顶点，就是平面图的不可避免顶点。这就是说任何平面图中可以没有度是大于等于6的顶点，但不可以没有度是小于等于5的顶点。有了不可避免顶点，也就决定了着色时总可以把最后的待着色顶点Ⅴ0放到度是小于等于5的顶点之上。也总可以把待着色的困局顶点V0从度是大于等于6的顶点移动到度是小于等于5的顶点之上。在不可避免的顶点中，当d＝0度时的顶点是不与任何顶点相邻的，这就是完全图K1，也是一个平面图，也可以是一个待着色的终局顶点Ⅴ0。
    5，给待着色顶点直接着色。直接的或者经过移动后，把待着色顶点V0放到了度是小于4的顶点之上，或者围栏顶所占用的颜色数小于四种时，就是终局构形。给终局顶点V0直接着上第四种颜色就可以了。顶点度是d＝0的图就是完全图K1，无围栏顶点，也不占用颜色，着色时直接给K1着上任一种颜色也就够用了。对于围栏顶点所占用的颜色数已达到4的困局待着色顶点V0，则得使用待着色顶点移动法进行着色了。
    6，待着色顶点移动的已知条件。构形中除了待着色的困局顶点V0和围栏顶点外，图中其他的顶点都是已经经过了4—着色的顶点，且其围栏顶点都是只占用了不超过三种颜色的。这可以说就是图中给出的已知条件。有了这个条件，就能说明待着色的困局顶点V0不但是可以移动的，而且还是可以由困局顶点转化成终局顶点的，也一定是可以着上四种颜色之一的。这就为解决四色问题，证明四色猜测的正确性创造了条件。
    7，待着色顶点移动法着色。
    ①条件。需要移动的待着色顶点Ⅴ0必须滿足条件d≥4和c＝4，这就是困局顶点Ⅴ0。待着色顶点移动的终点则必须是围栏顶点占用颜色数c＜4的顶点，这就是终局顶点V0。但转化为终局顶的这个顶点的围栏顶点原有的着色所占用的颜色数不但应有c＜4，而且还要滿足下列两个条件之一。一是围栏顶点至少有一个顶点是用了单一颜色的，以便在困局顶点Ⅴ0由该顶点移入到终局顶点时，围栏顶点仍只占用三种颜色，把第四种颜色直接给终局顶点着上即可。二是围栏顶点只占用了两种颜色（双色），以便在困局顶点Ⅴ0由任一个围栏顶点移入到终局顶点时，围栏顶点仍只占用三种颜色，把第四种颜色给终局顶点着上即可。不滿足者是不能成为终局顶点的。下面看看哪些顶点能滿足这样的两个条件呢？
    ②滿足以上两条件的顶点。度为d＝1的顶点，滿足有单色。度为d＝2的顶点，既滿有足单色又滿足是双色。度为d＝3的顶点，滿足有单色。度为d＝4的顶点，既滿足有单色又漏足是双色。度为d＝5的顶点，滿足有单色。以上五种度的顶点全都是平面图的不可避免顶点，所以说着色困局的待着色顶点V0不但一定可以移动到不可避免顶点上，而且是可以转化成终局待着色顶点的，是可以着上四种颜色之一的。度为d＝0的顶点虽然也是一个不可避免顶点，但其本身又是一个单独的平面图K1，在我们所研究的连通平面图中是不存在度为d＝0的不可避免顶点的。
    ③不满足以上两条件的顶点。在度为d≥6的顶点的围栏顶点原着色中，不一定也都有单色顶点，也不一定都是只占用了两种颜色的，所以当Ⅴ0移入后，不一定都可以转化成终局顶点，也就不可能都能着上四种颜色之一。还得再把V0继续移动到不可避免顶点上去。
    ④不满足中的特例。度为d＞4的偶度顶点都有可能出现围栏顶点只占用两种颜色的情况，度为d＞5的奇度顶点的围栏顶点也都有可能出现只有一个单色顶点的情况，所以V0顶点也是可以移动到这样的顶点之上的，也不一定非得都要移动到d≤5的不可避免顶点之上。
    ⑤个别特殊的图。若是只含有d＝4度的顶点（如八面体所对应的图）和只含有d＝5度的顶点（如二十面体所对应的图）时，V0顶点只能从d＝4的顶点移向d＝4的顶点或从d＝5的顶点移向d＝5的顶点。但移动前后的V0顶点的围栏顶点所占用的颜色数却是不同的。前者是c＝4，后者是c＝3。前者是不可着上四种颜色之一的，后者则是可以着上四种颜色之一的。
    ⑥两个极端情况。若是只有一个4度或一个5度的顶点，其他顶点都是度大于等于6的顶点的图时，正好困局顶点V0也就出现在了这个4度或5度的顶点之上时，就只得把Ⅴ0顶点先从低度顶点移向高度顶点，若这时的高度顶点是终局顶点时，问题也就解决了。否则，再把V0由高度顶点再移回低度的4度顶点和5度顶点，就一定是能够解决问题的。因为这时低度的4度或5度顶点的围栏顶点所占用的颜色数已不再是4，而是3了。
        以上所述，就说明了任何情况下的困局顶点V0都是一定可以移动到不可避免顶点之上，从而转化成终局顶点的，并且也都是可以着上四种颜色之一的。
    8，四色猜测是正确的。止此，各种情况下的待着色顶点，是终局顶点时，可以用直接着色的办法着上四种颜色一，是困局顶点时，待着色顶点V0则是可以通过移动转化成终局顶点，并都是可以着上图中已用过的四种颜色之一的。四色猜测也就被证明是正确的了。可以上升为四色定理了。

执笔；雷    明
二〇二三年四月五日于长安

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，