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

雷明85639720

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

数学家狄拉克1953年在其论文《k—色图的构造》一文中提出一个问题：对于任意大的一个正整数k，是否存在一个图，不包含三角形但色数是k？这一问题分别在1954年和1955年分别由勃兰克·斯德卡兹和米歇尔斯基独立的作出了回答。米歇尔斯基（Mycielski）给出的由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法是：设Gk的顶点是v1，v2，…，vn,，添加点u1，u2,…，un和点u0。将ui与vi所有相邻顶点及u0相连，1≤i≤n。如此得到的图就是一个不含三角形的k＋1色图。
这里所说的不含三角形的图实际上就是基图Gk的密度是小于3的图。米歇尔斯基的这一构造方法在图论界把它叫做Mycielski—操作，简称M—操作。M—操作过程又是可以递推的，即可以多次进行的。每进行一次M—操作，图的密度（或最大团）并不发生变化，但其色数却增加1。于是，就有了“存在无三角形且色数任意大的图”[4]的说法。实际上，进行M—操作时的基图的密度也可以是任意的，不一定都得是密度小于3的图。所以也就有“在各种密度下都有色数是无穷大的图”。请注意，这里所说的是图，不是只指“平面图”，而是指任意的“图”。
米歇尔斯基操作方法：是在有v个顶点的、色数是k的图以外，作一个有u个星点顶点的u—星（注意，u—星的总顶点数是u＋1），并使u＝v。然后再把u—星中的星点顶点ui（1≤i≤u＝v）与原图中与ui相对应的顶点vi的所有相邻顶点都与ui用边连接起来（注意，u—星的中心顶点u0是与原图中的任何顶点都不相邻的），这时所得到的图的色数就比原图的色数大1，且图中的最大团不变。
M—操作后，只所以最大团保持不变，是因为每个星点顶点ui都只和原图中与其对应的顶点vi的相邻顶点相邻，而与这个对应顶点vi并不相邻，所得到的团的顶点数仍与原图中最大团的顶点数是相等的。只所以所得图的色数一定比原图的色数大1，是因为u—星中的u个星点顶点均是不相邻的，他们可以同化（凝结）成一个顶点。这时，u个星点顶点所凝结成的这个顶点，又与原图中的所有顶点都相邻了，这个顶点也只能着以原图中所用颜色以外的另一种颜色（因为u—星的中心顶点与原图中的任何顶点都不相邻，所以给其着上原图中的任何一种颜色都是可以的）；另一个原因是，因为u—星的各星点顶点ui和原图中与其相对应的顶点vi均不相邻，可把这u个星点顶点分别着以和原图中与其相对应的顶点相同的颜色，这样u—星的u个星点顶点就占用完了原图中的所有颜色，剩下的u—星的中心顶点u0因与各星点顶点均相邻，所以就只能着以原图中所用颜色以外的另一种颜色了。
1、反证法的假设：
假设四色猜测是正确的，那么就一定有任何平面图的色数都是小于等于4的结论。若对某个平面图在进行了M—操作后，得到的图不再是平面图了，不管其色数是多少，就都不再是四色问题研究的对象了。因为有些非平面图色数的却是小于等于4的。如K3，3图的色数是2，虽然不大于4，但K3，3图却是一个典型的非平面图；若在M—操作后，得到的图仍是平面图，但其中只要有一个图的色数是大于4的，则就可以否定假设，得出四色猜测是不正确的结论；若在M—操作后，得不到有色数大于4的平面图，就应该肯定假设是对的，四色猜测是正确的。
2、图中无圈的情况（即只有一个面的情况的图）
当图是K1时，色数是1，M—操作的结果，色数比原图大1是2，虽不大于4，但却是一个含有K2团的、密度是2的、不连通的平面图。这一点是不符合M—操作的要求的（见图1）。

当图是K2时，色数是2，M—操作的结果，色数比原图大1是3，也不大于4，仍然是平面图（5—圈，见图2），该图同化后是一个K3图，所以色数是3。
当图是树时，色数仍是2，最简单的树——道路——进行M—操作的结果，色数比原图大1是3，也不大于4，也仍然是平面图，但密度增大了（由2变成了3），也不符合M—操作的要求（见图3）。
树图中只有很一少部分在M—操作后仍然是平面图，而大部分的树图在M—操作后，也都是非平面图，也就不是四色猜测所研究的对象了。

3、图中有圈的情况（即有两个以上面的情况的图）
当图是一个3—圈（即K3图）时，色数是3，M—操作的结果，色数比原图大1是4，但不大于4，图也仍是一个平面图，图中不但有3—圈，也有了4—圈（如图4），该图同化后是一个K4图，所以色数是4。
当图是一个4—圈时，色数是2，M—操作的结果，色数比原图大1是3，虽不大于4，但却成了一个非平面图（如图5），当然也已不再是四色猜测研究的对象了。
当图是一个5—圈时，色数是3，M—操作的结果，色数比原图大1是4，虽然也不大于4，但却也是一个非平面图（见图6），它也就不再是四色猜测研究的对象了。
可见，边数大于等于4的圈，进行了M—操作后的图，都会成为非平面图的，就不再是四色猜测研究的对象了。
4、除了2—圈（有平行边的K2团）和3—圈（即K3团）以外的面数大于2的图进行M—操作后都不再是平面图的证明
在对图进行M—操作时，先要作一个n—星图，为了保证图中不出现交叉边，仍是平面图，这个n—星就必须放在同一个面内。n—星的有关星点顶点若与位于该面边界上的顶点用边相连时，是不会产生交叉边的；但当n—星的有关星点顶点与位于该面边界以外的任何顶点用边相连时，就必然要产生相交叉的边，图也就变成了一个非平面图。因此，仍要保持在M—操作后的图是平面图时，原图中最多只能有两个面，即最多只能是有一个圈的图。
① 2—圈是一个2—重的K2图，因为平行边只相当于一条边，所以2—圈实际上就是K2图，色数是2。从图2知道，K2图M—操作后是一个5—圈，仍是一个平面图，其色数是3，比原来增大了1，但仍小于4。从图6又知道，5—圈进行了M—操作后是一个非平面图，所以2—圈进行第二次M—操作后就成了非平面图。
② 3—圈就是K3图，也从图4知道，K3图M—操作后仍是一个平面图。但因为K3图M—操作后，图中不但出现了不能再继续进行M—操作的4—圈，而且面数也是大于2的。所以，根据以上①和图5知道，K3图在进行了第二次M—操作后，也一定是一个非平面图，也不再是四色猜测研究的对象了。
③ 因此，面数是2的图，除了2—圈（有平行边的K2图）和3—圈（即K3图）外，在进行了M—操作后的图均是非平面图，也都不是四色猜测研究的对象了。含有轮的图中，其面数都是大于2的，所以含有轮的图在进行了M—操作后，也均不是平面图，也就不再是四色猜测研究的对象了。
M—操作后仍是平面图的图的必要条件是：面数是1的无圈图和边数（或顶点数）是小于等于3单圈图。
5、除K1图外的任何平面图第二次M—操作后都不再是平面图了
以上进行M—操作后仍是平面图的只有K1，K2，某些道路Pn和K3（即3—圈），现在再看这些图进行第二次M—操作的情况。
K1图M—操作一次后，是一个含有K2团的、不连通的平面图（见图1），色数是2；这个图再进行一次M—操作后，一定是如图2那样的图，是一个5—圈，也是平面图，色数是3，仍不大于4；但因5—圈进行M—操作后是一个非平面图（见图6），所以K1图在进行了三次M—操作后就成为了非平面图。
K2图M—操作一次后，是一个5—圈（见图2），色数是3。5—圈再进行M—操作后的图是一个非平面图（见图6），所以K2图在进行了两次M—操作后，也就成为了非平面图。
道路Pn在进行了一次M—操作后，所得到的图中既有3—圈，又有4—圈，但仍是平面图，色数也是3（见图3）。而这4—圈在进行M—操作后的图却是非平面图，所以说，在M—操作一次后仍是平面图的道路，在进行第二次M—操作后也都成了非平面图；
3—圈（即K3图）M—操作一次后，图中既有3—圈，又有4—圈（见图4），色数是4，也不大于4。因4—圈再进行M—操作后的图是非平面图（见图5），所以3—圈（即K3图）也是在进行了两次M—操作后，就成了非平面图。
除了以上这些图以外，其他任何平面图的面数都是大于2的。除了3—圈外的任何面数等于2的圈（平面图），在进行一次M—操作后的图都是非平面图，他们也都不再是四色问题所研究的对象了。
到此，就证明了除K1图外的任何平面图，在进行了第二次M—操作后，就都不再是平面图了。
6、四色猜测是正确的
以上我们对任意的平面图都进行了M—操作，M—操作后的结果仍是平面图的图的色数都是不大于4的，这就证明了开始的假设是正确的。任何平面图的色数都是不会大于4的，四色猜测是正确的。

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