用增加图的色数的方法证明四色猜测

雷明85639720

用增加图的色数的方法证明四色猜测
雷  明
（二○一七年三月十一日）

1  作一个图比原图的色数大1的方法
作一个图，使其色数比原图的色数大1的方法有两种。这两种方法，一个是米歇尔斯基操作法，另一个就是不可同化道路法。
1、1  米歇尔斯基操作法：是在有v个顶点的、色数是k的图外，作一个有v个星点顶点的v—星（注意，星的总顶点数是v＋1）。然后再把v—星中的星点顶点vi（1≤i≤v）和原图中与其相对应的顶点vi的所有相邻顶点都用边连接起来（注意，v—星的中心顶点v0是与原图中的任何顶点都不相邻的），这时所得到的图的色数就比原图的色数大1，且图中的最大团不变。
最大团保持不变，是因为每个星点顶点都只和原图中与其对应的顶点的相邻顶点相邻，而与这个对应顶点并不相邻。只所以所得图的色数一定比原图的色数大1，是因为v—星中的v个星点顶点均是不相邻的，他们可以同化（凝结）成一个顶点，这时，该顶点又与原图中的所有顶点都相邻了，这个顶点只能着原图中所用颜色以外的另一种颜色（因为v—星的中心顶点与原图中的任何顶点都不相邻，所以给其着上原图中的任何一种颜色都是可以的）；另一个原因是，因为v—星的各星点顶点和原图中与其相对应的顶点不相邻，均可着以和原图中与其相对应的顶点相同的颜色，这样v—星的星点顶点就占用完了原图中的所有颜色，剩下的v—星的中心顶点v0因与星点顶点均相邻，只能着以原图中所用颜色以外的另一种颜色了。
1、2  不可同化道路法：这里的“同化”即图论中的“收缩”，且只是指不相邻顶点间的收缩。“不可同化道路”是指图的某最大团外的一条道路，该道路总有一个顶点同化不到最大团中去。
若在一个最大团Kn外有一条道路，这条道路的所有顶点都与最大团中的同一个Kn－2团的各顶点均相邻，同时道路的两个端点顶点又分别与最大团中另一个K2团中有一个顶点相邻。这样，道路中除了两个端点顶点只能向那个K2团的某一个顶点同化外，道路中的其他顶点均是可向这个K2团中的任一个顶点同化。
当道路的两个端点顶点分别与K2团中的一个顶点相邻时，同时道路又是寄数顶点时，道路中总是有一个顶点同化不到最大团中去：而当道路的两个端点顶点与K2团中的同一个顶点相邻时，同时道路又是偶数顶点时，道路中也总是有一个顶点是同化不到最大团中去的。
道路有一个顶点同化不到最大团中去，就意味着最大团的顶点数增大了1。最大团是一个完全图，完全图的色数就等于其顶点数，所以最大团的顶点数的增大，也就意味着最大团的色数的增大了，这也就意味着图的色数增大了。
1、3  色数变大了的图，但只要图的最大团不变成K5而成为非平面图，且其色数又不会大于4，也就能说明四色猜测是正确的。
2  根据不可同化道路原理，证明四色猜测是正确的
2、1  色数为n的图一定可以同化为一个Kn图
根据已证明是正确的哈德维格尔猜想，一个色数为n的图，一定是可以同化为一个Kn图的。因为图中不相邻的顶点才可以使用同一颜色，而不相邻的顶点是可以同化为一个顶点的，所以哈德维格尔猜测想是正确的。
2、2  各种最大团的不可同化道路
一个色数是1的图同化后一定是一个K1团，按作不可同化道路使图的色数增大的方法，K1团作一条不可同化道路后的图是K2团，色数是2＜4；对这个K2团再作一条不可同化道路，是一个5—圈（或3—圈，即K3团），色数是3＜4；5—圈同化后，是一个K3团；对这个K3团再作一条不可同化道路，是一个5—轮（或3—轮，即K4团），色数是4≯4；5—轮同化后，是一个K4团；对这个K4团再作一条不可同化道路时，图就出现了交叉边，变成了非平面图，不再是四色猜测所研究的对象了。可见色数是1的图只能作三次不可同化道路，色数都不大于4。
用同样的方法可研究色数是2，3，4的图，分别只能作二次、一次和零次不可同化道路，其色数都是不会大于4的。否则再多作一次不可同化道路，不管其色数是否大于4，图都将成为非平面图，都不是四色问题所研究的对象了。
2、3  K4团作了不可同化道路后不再是平面图的证明
最大团K4团顶点数是4，边数是6；不可同化道路PN的顶点数是n，边数是n－1；K4团G与PN道路相邻的边数是2n＋2；整个系统的顶点数是4＋n，边数是6＋n－1＋2n＋2＝3n＋7；顶点数是4＋n的平面图最大顶点数只能是3×（4＋n）－6＝3n＋6；显然3n＋7＞3n＋6，所以K4团作了不可同化道路后，就不再是平面图了。
2、4  四色猜测是正确的
从以上对平面图的各种团都作了不可同化道路所得的图看，在没有出现交叉连前，即图没有变成非平面图之前，所有图的色数都是不大于4的。这就证明了任何平面图的色数都是不大于4的。四色猜测得到证明是正确的。
3  根据米歇尔斯基操作原理，用反证法证明四色猜测
    3、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。
3、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—操作；
道路Pn进行M—操作一次后，图中既有4—圈，又有5—圈，因这两种圈均不能进行M—操作，所以道路也是只能进行一次M—操作；
3—圈（即K4图）M—操作一次后，图中既有3—圈，又有4—圈，因4—圈不能进行M—操作，所以3—圈（即K4图）也只能进行一次M—操作。
3、3  四色猜测是正确的
以上我们对任意的平面图都进行了M—操作，M—操作后的结果仍是平面图的图的色数都是不大于4的，这就明了开始的假设是正确的。任何平面图的色数都是不会大于4的，四色猜测是正确的。


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

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

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，