根据米歇尔斯基操作原理，用反证法证明四色猜测

雷明85639720

根据米歇尔斯基操作原理，用反证法证明四色猜测
雷  明
（二○一七年二月二十四日）

    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，可以这样理解：① 由于增加的星形图的各个星点顶点均不相邻，所以这些星点顶点是可以同化成一个顶点的。这样，n个星点顶点同化后的这个顶点就与基图中着有各种颜色的顶点都相邻了。这个顶点只能着原基图中所用颜色以外的另一种颜色，使得M—操作后的图的色数比原基图的色数增大了1。而星形图的中心顶点u0又与基图中各顶点均不相邻，给其着以基图中已用过的任一种颜色就可以了。② 若把所增加的星形图中各星点顶点分别着以基图中所对应顶点的颜色，这时这些星点顶点也就用完了基图中已用过的颜色总数，星形图的中心顶点也就只能着以基图中已用过的颜色以外的另一种颜色了，使得M—操作后的图的色数也比原基图的色数增大了1。
2、平面图的M—操作
现在我们对任意的平面图进行M—操作：假设四色猜测是正确的，那么就有任何平面图的色数都是小于等于4的结论。若M—操作后，得到的图不再是平面图了，不管其色数是多少，就都不再是四色问题研究的对象了，因为色数小于等于4的图不一定都是平面图。如K3，3图，色数虽是2，但却是一个非平面图；若M—操作后，得到的图仍是平面图，但只要有一个的色数大于4，则就可以否定假设，得出四色猜测不正确的结论；若M—操作后，得不到色数大于4的平面图，就应该肯定假设是对的，四色猜测仍是正确的。
一次M—操作，图中只有一个面的情况时：
当图是K1时，色数是1，M—操作的结果，色数比原图大1是2，但不大于4，仍是平面图（但不连通），如图1；
当图是K2时，色数是2，M—操作的结果，色数比原图大1是3，也不大于4，也仍是平面图（5—圈）；


当图道路时，色数也是2，M—操作的结果，色数比原图大1是3，也不大于4，仍是平面图，图中既有4—圈，也有5—圈，如图3；
当图是树时，色数也是2，M—操作的结果，色数比原图大1是3，虽不大于4，但却成了一个非平面图，如图4。已不再是四色猜测研究的对象了；
当图中有两个面的情况时：
图是一个3—圈（即K4图）时，色数是3，M—操作的结果，色数比原图大1是4，但不大于4，仍是一个平面图，如图5；
图是一个4—圈时，色数是2，M—操作的结果，色数比原图大1是3，虽不大于4，但却成了一个非平面图，如图6；也已不再是四色猜测研究的对象了；

图是一个5—圈时，色数是3，M—操作的结果，色数比原图大1是4，虽不大于4，但却也成了一个非平面图，如图7；也已不再是四色猜测研究的对象了；
可见边数大于等于4的圈，是不能进行M—操作的，否则，图就变成了非平面图了，就不再是四色猜测研究的对象了。
当图中的面数大于2时：
M—操作时，要先画一个星，该星只能位于一个面内。若图中有边数大于等于4的面（即4—圈）时，这个面M—操作后就是一个非平面图，所以含有边数大于等于4的圈的图，都是不能进行M—操作的；
若图是一个三角剖分图，所有面全是3—圈，该星的有关星点顶点与位于该面边界上的顶点用边相邻时，是不会产生相交叉的边；但当该星的有关星点顶点与位于该面边界以外的顶点用边相邻时，必然要产生相交叉的边，也使图就变成了一个非平面图；
因此，图中面数大于2是的图，均是不能进行M—操作的；
含有轮的图中，其面数都是大于2的图，所以含3—轮（即K4团）的图一定也是不能进行M—操作的；
以上M—操作后的图仍是平面图的只有K1，K2，道路和K3（即3—圈），现在再看其是否还可以进行第二次M—操作：
K1图M—操作一次后，是一个含有K2图的平面图，色数是2；这个图再进行一次M—操作后，一定是如图2那样，是一个含有5—圈的图，色数是3，仍不大于4；但因5—圈不能进行M—操作，所以K1图也只能进行两次M—操作；
K2图M—操作一次后，是一个5—圈，5—圈不能进行M—操作，所以K2图也只能进行一次M—操作；
道路M—操作一次后，图中既有4—圈，又有5—圈，因这两种圈均不能进行M—操作，所以道路也是只能进行一次M—操作；
3—圈（即K4图）M—操作一次后，图中既有3—圈，又有4—圈，因4—圈不能进行M—操作，所以3—圈（即K4图）也只能进行一次M—操作。
3、四色猜测是正确的
以上我们对任意的平面图都进行了M—操作，M—操作后的结果仍是平面图的图的色数都是不大于4的，这就明了开始的假设是正确的。任何平面图的色数都是不会大于4的，四色猜测是正确的。

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

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

雷明85639720

，，，，