平面图最小完全同态的顶点数是不大于4的——四色猜测证明方法之一

雷明85639720

平面图最小完全同态的顶点数是不大于4的
——四色猜测证明方法之一
雷  明
（二○一六年十月二十九日）

1、哈德维格尔猜想与哈拉里的结论
哈德维格尔猜想是：色数为n的图，最终可以同化（也即收缩。把图中不相邻的顶点凝结在一起的过程叫同化）为一个完全图Kn。这很容易证明，因为相同颜色的顶点一定是不相邻的，他们是可以同化为一个顶点的，所以同化的结果——完全图Kn——中一定有n个顶点；Kn中n个顶点均相邻是因为这n个顶点中，每一个顶点代表的是若干个在原图中不相邻、但又是着有相同颜色的顶点，且其中至少有一个顶点是与这个完全图Kn中的其他顶点是相邻的。
哈拉里也说过，图的色数等于图的最小完全同态的顶点数。把图中不相邻的顶点同化一次所得到的图就叫原图的一个同态；经过一系列的同化后，就会得到一个完全图，这就是原图的完全同态；在不同的完全同态中，顶点数最少的一个，就是原图的最小完全同态。
哈拉里与哈德维格尔是从同一回事的两个不同的方向说起的。哈德维格尔说的是把色数为n的、着色好色的图，经同化后最终可得到一个完全图Kn；而哈拉里则说的是把图进行同化，最后一定会得到一个顶点数最少的最小完全同态Kn，其顶点数n也就是图的色数。
可以看出，我们只要能证明平面图的最小完全同态的顶点数是不大于4的，就可使四色猜测得到证明是正确的。
2、任意图的最小完全同态的顶点数
任何图都有一个最大团，最大团的顶点数就是图的密度。现在我们首先看图中有没有不可同化到最大团中去的顶点。
设最大团是Kn，若其外有一条道路Pn，该道路的每一个顶点均与最大团中Kn相同的n－2个顶点相邻，道路的两个端点顶点又分别与最大团Kn中的其他两个顶点之一相邻，如图1（为了使图面清晰，图中最大团Kn中的那个Kn－2团与道路Pn中各顶点间的相邻关系均未画出）。按给出的条件，道路Pn中的任何顶点都是不可能同化到最大团Kn中的那个Kn－2团中去，而只能向剩下的那个K2团中去同化。这就把一条道路Pn向最大团Kn的同化转变成了向K2团的同化问题了。

在图1，a中，当道路的顶数n为奇数（或在图1，b中，当道路的顶点数n为偶数）时，道路Pn中总有一个顶点同化不到最大团Kn中的那个K2团中去，也即同化不到最大团Kn中去。把这样的顶点叫不可同化顶点。可见道路Pn中各顶点的不可同化的机会是相等的，即每一个顶点都可以作为这样的不可同化顶点。这时图的最大团就由原来的Kn变成了Kn＋1，图同化的最后结果就是一个Kn＋1完全图，这就是原图的最小完全同态，其顶点数n＋1就是图的色数。把这样的、总有一个顶点同化不到最大团中去的道路就叫不可同化道路。这时，图中的最大团就不再是原来的Kn而变成了Kn＋1，整个图中也就只有这一个Kn＋1团是最大的，当然其他的任何顶点也都一定是可以同化到这个最大的Kn＋1团中来的，所以说这个图的最小完全同就是Kn＋1团，顶点数是n＋1。
最大团外最多能有多少条不可同化道路呢？如果如果最大团外有S条不可同化道路，当各道路没有构成联时（联是一个图的所有顶点都和另一个图的任何顶点都相邻的图），各道路间总有不相邻的顶点存在，把这些顶点做为不可同化顶点是一定能够办到的。然后再把这S个不可同化顶点同化在一起，仍相当于只有一条不可同化道路的情况；如果这S条不可同化道路间已经构成了联时，则这S个不可同化顶点间，因其本身就是相邻的而不能再同化成一个顶点，就产生了S 个不可同化顶点。
这S条不可同化道路有没有上界呢？回答是，一定有。S条不可同化道路的联在图中也只是一个分子图，该分子图的密度2S（联的密度是构成联的各图的密度之和，道路的密度是2，所以S条道路的密度之和就是2S）是不会大于图的密度的，即是不会大于图的最大团的顶点数n的。所以有2S≤n和S≤n/2。可以看出，任意图的最小完全同态的顶点数是不会大于原图的最大团的顶点数的1.5倍的。
3、平面图的最小完全同态的顶点数不大于4
一个Kn团与其外一条不可同化道路Pn的总边数是：Kv团的边数有v（v－1）/2条，不可同化道路Pn的边数有n－1条，Kv团和Pn道路间的相邻边数有n（v－2）＋2条，三者的总边数和是v（v－1）/2＋n－1＋n（v－2）＋2＝v（v－1）/2＋n－1＋nv＋2n＋2＝v（v－1）/2＋3n＋1。
因为平面图的最大团是K4，最大密度也是4，当把v＝4代入上式v（v－1）/2＋3n＋1后得，K4团与一条不可同化道路Pn的总边数应是6＋3n＋1，而实际上在平面图的情况下，一个K4团与一条顶点数为n的道路Pn的总顶点数是4＋n，这4＋n个顶点的最大边数却是不会大于3（4＋n）－6＝12＋3n－6＝6＋3n的，显然前者6＋3n＋1是大于后者6＋3n的。这就说明了密度为4的平面图的最大团K4外是不可能有不可同化道路的，其最小完全同态的顶点数是不会大于4的。
对于密度小于4的平面图：当图密度是3时，最大团和不可同化道路的总边数应是4＋3n，K3团与Pn道路总共有3＋n个顶点，在平面图中最大只可能有9＋3n－6＝3＋3n条边，小于4＋3n；当图的密度是2时，最大团和不可同化道路的总边数应是2＋3n，K2团与Pn道路总共有2＋n个顶，在平面图中最大只可能有6＋3n－6＝3n条边，小于2＋3n；当图的密度是1时，最大团和不可同化道路的总边数应是1＋3n，K1团与Pn道路总共有1＋n个顶，在平面图中最大只可能有3＋3n－6＝3n－3条边，小于1＋3n；以上这些，都说明了在密度小于4的平面图中，最大团外是可以存在不可同化道路的，但最多只可能有一条（这个1均分别不大于其密度1，2和3的1.5倍），这是因为两条道路的联的密度是4（＝2×2），已不符合这里所说的密度小于4的平面图的条件了。这也就说明了密度小于4的平面图的最小完全同态的顶点数也是不会大于4的。
到此，已经证明了任何平面图的最小完全同态的顶点数都是不大于4的，也就证明了四色猜测是正确的。
3、平面图的（顶点）着色数的判定
密度为4的平面图，因其最小完全同态的顶点数总不会大于4，所以密度是4的平面图的色数只能是4（不大于4）；密度为3的平面图中若含有奇轮，而奇轮中有一条K3团的不可同化道路，所以密度是3的平面图的色数最大只能是4，否则色数则是3（均不大于4）；密度为2的平面图中若含有奇圈，而奇圈中有一条K2团的不可同化道路，所以密度是2的平面图的色数最大只能是3，否则色数则是2（也均不大于4）；密度为1的平面图K1，是一个孤立顶点，1种颜色就够用了（也不大于4）。

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

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

雷明85639720

,,,,,,,,

雷明85639720

，，，，，

雷明85639720

，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

谢谢你了。