M—操作不影响四色猜测的证明

雷明85639720

M—操作不影响四色猜测的证明
雷  明
（二○一五年十二月十日）

【摘  要】 从进行了M—操作后仍是平面图的图的色数都不大于4，就可以证明了四色猜测是正确的。
【关键词】四色猜测  米歇尔操作  M—操作  图的密度  图的色数

M—操作是米歇尔斯基操作的简称。对一个顶点数是v的图G，添加一个星点数u＝v的u—星（注意：u—星有u＋1个顶点），把u—星的u个星点顶点ui与图G中对应顶点vi的相邻顶点用边连接起来，这就是M—操作。M—操作所得到的图的密度（图中最大团的顶点数）不变，但色数却比原图G增大了1。又加上M—操作是可以连续进行的，于是便有“无三角形而色数任意大的图”的说法。那么这是不是说四色猜测就无法证明了呢。不是的。
首先要明白四色猜测研究的对象是在平面图（平面图的密度都不大于4，密度是图中最大团的顶点数）范围以内的图。只要不是平面图，不管他有无三角形，也不管他的色数是多大，就都再不是四色问题研范围内的对象了。
现在对密度不大于4的平面图进行M—操作，看其结果是什么，看是不是还有平面图范围之内。
对于密度为4的K4图，经M—操作后的图，顶点数是4＋4＋1＝9，边数是6＋3×4＋4＝22。而顶点数是9的平面图边数最大只可能是3×9－6＝21，22＞21，显然K4图进行M—操作后是一个非平面图，就不再是四色问题研究的对象了。说明密度是4的平面图的色数是不可能大于其最大团K4团的顶点数4的。
对于密度为3的K3图，经M—操作后的图，顶点数是3＋3＋1＝7，边数是3＋2×3＋3＝12，而顶点数是7的平面图边数最大是3×7－6＝15，显然K4图进行M—操作后仍是一个平面图，画图后的确也是如此。现在再看看该图是否还能再进行一次M—操作呢。在未进行M—操作之前，我们先这样进行分析：顶点数是7的图中，边数是最多的是15，而顶点数是7，边数比15少的图中一定含有边数大于等于4的圈，如果4—圈进行了M—操作后是非平面图，则这个图就不能再进行M—操作了。4—圈进行M—操作后，顶点数是4＋4＋1＝9，边数是4＋2×4＋4＝16，而顶点数是9的平面图边数最大是3×9－6＝21，16虽然不大于是21，但从作图中可以看出，该图是不可以画在平面上的（图读者自已画一画），即图中已出现了不可避免的交叉边。正象K3，3图一样，虽然图的边虽没有达到3v－6，但也不是平面图了。这样以来，K3图也只能进行一次M—操作，说明密度是3的平面图的色数最大也只能是比最大团K3团的顶点数（密度）3大1，成为4，但仍不大于4。
对于密度为2的K2图，经M—操作后的图，顶点数是2＋2＋1＝5，边数是1＋2×1＋2＝5，这是一个密度是2的5—圈。显然K2图进行M—操作后仍是一个平面图。这个图还能进行一次M—操作否？肯定是不可能了。因为上面已经知道，4—圈进行了M—操作后已是非平面图了，所以5—圈进行了M—操作后的图也一定不是平面图。这不但说明了K2图也只能进行一次M—操作，也说明了密度是2的平面图的色数最大也只能是比最大团K2团的顶点数（密度）2大1，成为3，也是小于4的。
密度为1的K1图，经M—操作后的图，成了K2图，密度发生了变化，但仍然是平面图，K2图再进行一次M—操作后，成了5—圈，5—圈再进行一次M—操作后，成了非平面图，所以K1图只能进行两次M—操作。从上面可知，密度为2的平面图的色数最大只能是3，所以密度为1的平面图在进行了两次M—操作后的图的色数最大也只能是3，仍然是小于4的。
现在已经证明了任何一个平面图在进行了M—操作后，只要仍是平面图时，其色数都是不大于4的，这也就证明了四色猜测是正确的。

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

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