不用“不可免集” 证明四色猜测的四种方法

雷明85639720

不用“不可免集”证明四色猜测的四种方法
雷  明
（二○一七年元月三十一日）

    1、用哈德维格尔猜想来证明
哈德维格尔猜想已经被子证明是正确的，我们完全就可以利用这个猜想或者叫做定理来证明四色猜测了。
哈德维格尔猜想说：任何色数是n的图，一定可以同化（即收缩运算，就是把图中不相邻的顶点凝结在一起的过程）为一个完全图。因为四色问题研究的对象是平面图，所以我们首先要假设图是一个亏格是0的、色数是n的平面图。根据哈德维格尔猜想，这个图一定是能同化为一个完全图 Kn的，这个完全图Kn的亏格也一定是0，是一个平面图，否则就与假设发生了矛盾。
已知平面图中最大的完全图是K4，即在平面图中，所有完全图的顶点数n都是小于等于4的。所以也就有原图的色数n也是小于等于4的。而原图我们已经假设它是亏格为0的平面图了，所以这就证明了任何平面图的色数都是小于等于4的。四色猜测是正确的。
证毕。
2、用图的色数一定等于图的最小完全同态的顶点数来证明
哈拉里在他的《图论》一书中说：任意图的色数一定等于它的最小完全同态的顶点数。所谓完全同态就是利用同化运算把图变成一个顶点数最少的完全图，这个完全图就是原图的最小完全同态。显然，同化时一定是把不相邻的顶点凝结在一起的，当然最后的最小完全同态的顶点数就一定是原图的色数了。
同样也是因为四色问题研究的对象是平面图，所以我们首先要假设图是一个亏格是0的、色数是n的平面图。当然其最小完全同态的亏格也一定是0，是一个平面图，否则也就与假设发生了矛盾。
平面图中完全图的顶点数一定是小于4的，所以平面图的最小完全同态的顶点数也一定是小于等于4的，根据哈拉里说的任意图的色数一定等于它的最小完全同态的顶点数的理论，也就证明了任何平面图的色数都是小于等于4的。四色猜测确的。
证毕。
3、用不可同化道路的条数小于等于图的密度的一半来证明
不可同化道路是图的一个最大团外的一条道路。该道路中总有一个顶点同化不到最大团中去。如一个5—圈，最大团是K2，一个K2外的其他顶点中，总有一个顶点是不能同化到K2团中去的。若有S条这样的道路构成了联时，就应有S个顶点同化不到最大团中去。但这S条道路的联的密度（即联中最大团的顶点数，它是构成联的各条道路的密度2之和）2S一定是小于等于图的密度（图中的最大团的顶点数）ω的，即有2S≤ω，所以有S≤ω/2。
由于图的色数一定是不会小于图的最大团的顶点数的，所以图的色数γ的下限是ω≤γ，同化不到最大团中去的顶点的颜色，必须用最大团各顶点所用颜色以外的颜色，所以图的色数的上限是γ≤ω＋S≤ω＋ω/2≤1.5ω。因此就有图的色数的界是ω≤γ≤1.5ω。
因为四色问题研究的对象是平面图，而平面图的密度一定是小于等于4的，即平面图中最大团的顶点数一定是小于等于4的。把平面图的密度ω＝1，ω＝2，ω＝3分别代入图的色数的界ω≤γ≤1.5ω中，都有γ≤4的结果，不可同化道路的条数S最大都只能是1，都小于等于2和3的一半；而把ω＝4代入ω≤γ≤1.5ω中时，就出现有γ＞4的可能，但我们可以证明在密度ω＝4的平面图中，根本就不可能有不可同化道路，即S＝0。
这里首先要把不可同化道路与最大团的关系再说明一下：设最大团的顶点数是ω，不可同化道路的顶点数是n，这n个顶点均与最大团中的ω－2个顶点相邻，不可同化道路的两个端点顶点又分别与最大团中的另外两个顶点之一相邻。这样的道路中一定有一个顶点是同化不到最大团中去的。
这个最大团与不可同化道路构成的系统中，顶点数是ω＋n个，其边数总数是：①　最大团的边数ω（ω－1）/2，②　不可同化道路的边数n－1，③　二者相邻的边数2n＋2三者之和。即系统的边数是ω（ω－1）/2＋n－1＋2n＋2＝（ω－1）/2＋3n＋1。当ω＝4，上式就成为6＋3n＋1＝7＋3n，而顶点数是4＋n的平面图的最大顶点数是3（4＋n）一6＝12＋3n－6＝6＋3n＜7＋3n。图就不再是平面图了。所以，密度是ω＝4的平面图中，就不可能有不可同化道路的存在。其色数也就不可能大于最大团的顶点数4。
综上所述，各密度条件下的平面图的色数都不大于4，这就证明了四色猜测是正确的。
4、用米歇尔斯基操作来证明
米歇尔斯基操作（简称M—操作）是一个作图的方法。是作一个图的色数比原图的色数大1的方法。该方法是：在顶点数是n的原图外，作一个n—星，使星的中心顶点v0不与原图的任何顶点相邻，星点顶点ui只与其所对应的原图中的vi顶点的相邻顶点相邻（ui与vi并不直接相邻），这样得到的图的色数比原来的图的色数大1，但图中的最大团的顶点数却并不增大。如一个K2图的色数是2，进行了M—操作后得到一个5—圈，这个5—圈的色数是3，比原图K2图的色数大1，但其最大团仍是K2，最大的顶点数仍是2。
从以上M—操作的定义可以看出，密度是2的平面图的色数最大也只能是3，只能比其最大团的顶点数（密度）大1。因为对顶点数大于等于4的圈进行M—操作后，图就不再是平面图而是非平面图了。所以说密度是2的平面图的色数是不会大于3的。
一个K3图（3—圈）的色数是3，进行了M—操作后得到一个既有3—圈，又有4—圈的平面图，色数是4，比原图大1。同样，也因为对顶点数大于等于4的圈进行M—操作后，图就不再是平面图而是非平面图了。所以说密度是3的平面图的色数是不会大于4的。
一个K4图（3—轮）的色数是4，进行了M—操作后得到的是一个非平面图，所以说密度是4的平面图是不能进行M—操作的，否则图就不再是平面图而是非平面图了。这也说明了密度是4的平面图的色数是恒等于4的。
至于K1图（平凡图），其色数是1，在进行了M—操作后得到的图的色数虽然是2，但得到的图却是一个密度是2的、不连通的平面图，图的最大团发生了变化，所以说密度是1的平面图也是不能进行M—操作的。
综上所述，在各种条件下的平面图，进行了M—操作后，所得到的图仍是平面图时，其色数都是不大于4的，这也就证明了四色猜测是正确的。
顶点数大于等于4的圈，在M—操作后所得的图不再是平面图的证明：
n—圈的顶点数是n，边数也是n；n—星的顶点数是n＋1，边数是n；n—圈的一个顶点都与两个顶点相邻，所以n—星的每一个星点顶点都与2n个顶点相邻。这样一个n—圈的M—操作系统图中：顶点数是n＋n＋1＝2n＋1个，边数是n＋n＋2n＝4n条。2n＋1个顶点的平面图的最大边数只可能是3（2n＋1）－6＝6n＋3－6＝6n－3条。当n＝4时，图的边数则是4×4＝16，虽然不大于其是平面图时的最大边数6×4－3＝21，但图中已明显的产生了不能去掉的交叉边。是一个非平面图了。这就证明了顶点数大于等于4的圈，在M—操作后所得的图就不再是平面图了。
边数大于3v－6的图一定不是平面图，但边数小于等于3v－6的图却不一定都是平面图，比如K3，3图，有6个顶点，9条边，小于3×6－6＝12，但K3，3却是一个典型的非平面图。
K4团在M—操后所得的图不再是平面图的证明：
K4团的顶点数是4，边数是6；4—星的顶点数是5，边数是4；M—操作所增加的边数是4×3＝12（一个星点与K4团中的三个顶点相邻）。系统总顶点数是9，边数是22。大于9个顶点时是平面图的最大边数21，显然就不再是平面图了。这也就证明了K4团在M—操后所得的图也就不再是平面图了。

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

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

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

谢谢朋友的支持。

雷明85639720

谢谢朋友的支持。

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，