Mycielski—操作与平面图的色数——四色猜测证明方法之七

雷明85639720

Mycielski—操作与平面图的色数
——四色猜测证明方法之七
雷  明
（二○一六年十月三十一日）

Mycieski（米歇尔斯基）—操作是一种可以保持图的密度不变，即最大团不变，但色数却比操作前增大1的构造图的操作方法。
1、Mycieski（米歇尔斯基）—操作
数学家狄拉克1953年在其论文《k—色图的构造》一文中提出一个问题：对于任意大的一个正整数k，是否存在一个图，不包含三角形但色数是k？这一问题分别在1954年和1955年分别由勃兰克•斯德卡兹和米歇尔斯基独立的作出了回答。米歇尔斯基（Mycielski）给出的由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法是：设Gk的顶点是u1，u2，……，un,，添加点v1，v2,……，vn和点v0。将vi与ui所有邻点及v0相连，1≤i≤n。如此得到的图就是一个不含三角形的k＋1色图。这里所说的不含三角形的图实际上就是基图Gk的密度是小于3的图。米歇尔斯基的这一构造方法在图论界把它叫做Mycielski—操作，简称M—操作。且这一操作过程是可以递推的，即可以多次进行的。每进行一次M—操作，图的密度并不发生变化，但其色数却增加1。于是，就有了“存在无三角形且色数任意大的图”的说法。实际上，进行M—操作时的基图的密度可以是任意的，不一定都得是密度小于3的图。
我们通过对米歇尔斯基操作的研究认为，M—操作实质上是对一个顶点数为v的连通图G（基图），增加一个星点数u＝v的u—星（注意：u—星有u＋1个顶点，星的密度是2），该星形图的点数u比基图的顶点数多1，即u＝v＋1。然后，把u—星的u个星点顶点ui与图G中对应顶点vi的所有相邻顶点用边连接起来（注意：但ui与vi并不连接），这就是M—操作。使每一个星点顶点ui最多只能与基图中含有vi顶点的最大团Kn中的n－1个顶点相邻，以保证图的密度不变。请注意，星形图的中心顶点u0与基图G中的任何顶点都是不相邻的。
M—操作后所得图的色数只所以比原基图的色数增大1，可以这样理解：① 由于增加的星形图的各个星点顶点均不相邻，所以这些星点顶点是可以同化成一个顶点的，这样，v个星点顶点同化后的这个顶点就与基图中着有各种颜色的顶点都相邻了，这个顶点只有着原基图中所用颜色以外的另一种颜色，使得M—操作后的图的色数比原基图的色数增大了1。而星形图的中心顶点u0又与基图中各顶点均不相邻，给其着以基图中已用过的任一种颜色就可以了。② 若把所增加的星形图中各星点顶点分别着以基图中所对应顶点的颜色，这时这些星点顶点也就用完了基图中已用过的颜色数，星形图的中心顶点也就只能着以基图中已用过的颜色以外的另一种颜色了，使得M—操作后的图的色数比原基图的色数增大了1。
    2、Mycieski—操作与四色猜测的关系
既然M—操作能保持原图的密度不变，其色数可以比原图增大1，那么我们可以对平面图的各种大小的团进行一下M—操作，看其色数增加后是否大于4，且图是否还是平面图。若进行了M—操作后的图的色数不大于4，且图又仍是平面图时，则四色猜测就是正确的；若M—操作后的图的色数大于4，但图仍是平面图时，则猜测就是不正确的。
3、对平面图各种团进行M—操作
平面图中一共有四种团，即K1，K2，K3和K4，各团的色数与其顶点数是相同的。现在一个个地对其进行M—操作，如图1。

    ①  K4团：M—操作后是一个非平面图（图中不但出现了在顶点以外边与边相交叉的情况，且9个顶点，应有3v－6＝21条边，而实际上图中已是22条边了），不是四色猜测研究的对象了。所以含有K4团的平面图的色数一定是其顶点数4≯4；
②　K3团：M—操作后还是一个平面图，色数是4，不大于4，但图中含有4—圈，从图1中可以看出，4—圈在M—操作后却是一个非平面图（图中出现了在顶点以外边与边相交叉的情况），也不是四色猜测测研究的对象了。所以K3团只能进行一次M—操作，色数最大是4≯4。因此，含有K3团的平面图的色数一定是小于等于4的；
③　K2团：M—操作后也是一个平面图的5—圈，色数是3，也不大于4，但对5—圈再进行一次M—操作时，从图1中也可以看出，得到的也是一个非平面图（图中也出现了在顶点以外边与边相交叉的情况），也不再是四色猜测研究的对象了。所以K2团只也能进行一次M—操作，色数最大是3≯4。因此，只含有K2团的平面图的色数也一定是小于4的；
④　K1团：K1团不可进行M—操作，因为K1团的密度本身只是1，而1—星本身的密度却是2，进行了M—操作后，虽然色数也增加了1，但图的密度也由1必然要增大到2，不符合M—操作密度不变的要求。而K1就只是一个孤立的顶点，一种颜色也就够用了。
4、四色猜测是正确的
综上所述，可以看出任何平面图（顶点）着色时，四种颜色一定够用了。这也就证明了四色猜测是正确的。这与用同化理论证明得出的结果一模一样。同化理论中K1团没有不可同化道路，色数只能是1；而这里K1团也不能进行M—操作，色数也只能是1。同化理论中K2团最多只有一条不可同化道路，密度是2的图的色数最大只能是3；而这里K2团也只能进行一次M—操作，密度是2的图的色数最大也只能是3。同化理论中K3团最多也只有一条不可同化道路，密度是3的图的色数最大只能是4；而这里K3团也只能进行一次M—操作，密度是3的图的色数最大也只能是4。同化理论中K4团是不可能有不可同化道路的，密度是4的平面图的色数也只能是4；而这里K4团也是不能进行M—操作的，密度是4的平面图的色数最大也只能是4。都说明了任何平面图的色数都是不大于4的。四色猜测是正确的。


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

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

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

谢谢了。

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，