平面图顶点着色色数的上界

——对四色猜测的再次证明

雷  明

（二○一二年七月三日）

    1、从任意图的角度看，图顶点着色的色数是没有上界的

我们通过对图的最小完全同态的研究，得到了一个公式：即任意图最小完全同态的顶点数与图的密度的关系

    α＝ω＋S≤ω＋［ω/ 2］≤［1.5ω］              （1）

式中α是图的最小完全同顶点数，ω是图的密度，即最大团的顶点数，S是图中某最大团外的不可同化道路的条数。所谓不可同化道路即是该道路中总有一个顶点是同化不到最大团中去的道路；这些道路的联即是任一条道路中的各个顶点都与其他道路中的所有顶点都相邻；由于有联的存在，而联中的各个顶点都是相邻的，所以各个同化不到最大图中去的顶点也就不可能再同化成一个顶点，所以有α＝ω＋S。［］表示其中的数字向下取整，即不大于［］中数字的最大整数。

由于图顶点着以的色数与其最小完全同态的顶点数是相等的，所以（1）式还可以写成

        γ＝α＝ω＋S≤ω＋［ω/ 2］≤［1.5ω］          （2）

这看上去好象就应是任意图顶点着色色数的界，但实际上却有Mycieiski—图以及通过Mycieiski—操作过程递推而得到的图的色数与（2）式不符，它说明了任意图的色数有不存在上界的可能性。

厦门大学图论博士×××老师这样说：“Mycielski构造的图说明：存在无三角形且色数任意大的图。”这个“无三角形”实际上就是密度不大于2 的图。杨博士还说：“Mycieiski—操作可以以任何图为基图，而不是仅仅以圈为基图，Mycieiski—操作的结果就是使得所得图比基图色数增加1。”这就可以把我们在上面得到的（2）式与Mycieiski—操作联系在一起，而得到任意图顶点着色色数的一个新的公式：

      ω≤α＝β＝γ＝γ_基图＋i＝ω＋S＋i_m＝［1.5ω］＋i_m   （3）

（3）式中γ_基图和i分别是基图的色数和Mycieiski—操作的次数。这就是任意图顶点着色色数的公式。http://s4/mw690/61aec5afge0e89f7ad993&690    的确，我们也已经画出了以5—轮（其密度是2，色数是3）为基图而经过了两次Mycieiski—操作过程的、密度仍为2的、但必须用5 种颜色（色数是5）来着色的Mycieiski—图（如图1）；同时也画出了以有两条已构成联的不可同化道路的K₄图为基图而只用了一次Mycieiski—操作过程的、密度仍为4的、但必须用6 种或7种颜色（色数分别是6 和7）来着色的Mycieiski—图（如图2）；它们的色数都是符合按公式（3）的计算结果的；但是这些Mycieiski—图却都是非平面图。

http://s12/mw690/61aec5afge0e8a2d6fa3b&690    我们又发现：Mycieiski—图的基图若是圈时，当m—数为0（即0—圈，圈中没有任何顶点）时的Mycieiski—图是平凡图K₁，密度是1，色数也是1；当m—数为1（即1—圈，圈中只有一个顶点，是一个环）时的Mycieiski—图是一个端点顶点带有一个环的P₃道路，密度是2，色数也是2；当m—数为2（即2—圈，圈中有两个顶点，是一个2—重的K₂图，是两条平行边）时的Mycieiski—图的密度是3，色数也是3；以上的这三种Mycieiski—图都是平面的，色数都不大于其密度；其后的以圈为基图的Mycieiski—图的密度都是2，且都是非平面图，色数则是：当m—数是偶数时的Mycieiski—图的色数都是偶圈的色数2加1，而当m—数是奇数时的Mycieiski—图的色数都是奇圈的色数3加1。进行了Mycieiski—操作后所得的图的顶点数是原基图顶点数的2 倍加1。见图3。

我们还发现这些Mycieiski—图以及通过Mycieiski—操作过程递推而得到的所有Mycieiski—图，无论其基图的密度是多少，这些图都已经是非平面图了，并且其色数是在我们得到的色数的上界之上随Mycieiski—操作次数的多少而增加的。

http://s10/mw690/61aec5afge0e8a5534609&690图3中各图的色数都是符合上面的公式（3）的。

如m—数是5的Mycieiski—图，其基图是5—圈，密度是ω＝2，其中有一条不可同化道路，即S＝1，基图的色数γ_基图＝ω＋S＝2＋1＝3≤［1.5ω］＝［1.5×2］＝［3］＝3。而在进行了一次M—操作后所得到的m—数是5的Mycielski—图的色数则是γ＝γ_基图＋i＝3＋1＝4。见图3，f；若基图的密度仍是2，但图中没有不可同化道路时，其色数则是2，在进行了一次M—操作后所得到的m—数是2和4的Mycielski—图的色数则分别是γ＝γ_基图＋i＝2＋1＝3。如图3，c和图3，e；若基图的密度是3，图中也没有不可同化道路，其色数则是3，在进行了一次M—操作后所得到的m—数是3的Mycielski—图的色数则是γ＝γ_基图＋i＝3＋1＝4。如图3，d。

还有仍以5—圈为基图，在进行了两次Mycielski—操作后所得到的Mycielski—图的色数则是γ＝γ_基图＋i＝3＋2＝5。如图1。

又如同样密度都是4的图，一个没有不可同化道路，而一个却有两条不可同化道路，且构成了联，其色数一个是4，一个是6，而对两图分别进行一次M—操作后所得到的图，一个色数是5，一个色数是7。如图2。

我们在这里研究的却是平面图的四色问题，而平面性的Mycieiski—图只有基图是圈的m—数为0，1和2的三种，这三种Mycieiski—图的色数都不大于其密度，正好都符合我们上面得到的公式（2）γ≤［1.5ω］。但公式（2）是不是就是平面图顶点着色色数的上界呢，还需要进一步的验证，看各种密度下的平面图的色数是不是符合γ≤［1.5ω］的上界。但不管怎样，至少可以确定任意图的色数是可以比图的密度大的。只要图的色数可以比其密度大1时，这对于证明猜测就已经够用了。

对于公式（3），只能说明任意图顶点着色的色数是没有上界的，还有没有别的用途，我还看不出来。但知道它可以用来判断一个已知色数的图在进行了若干次M—操作后所得图的色数罢了。

2、从平面图的角度看，平面图的色数却是有其上界的

由于平面图的密度都不大于4，这就使得我们有可能对平面图的密度一个个的进行研究，这就使一个本来对于图的密度来说是一个无穷的问题变成了一个有穷的问题。

由于图的色数等于图的最小完全同态的顶点数，该最小完全同态的顶点数又是图的密度与不可同化道路条数的和，所以检验平面图顶点着色色数上界的方法就是看某密度ω条件下的平面图中是否可以存在不可同化道路，且可以构成联的不可同化道路的条数S最多可以是多少。再看S与该图的密度ω之和的值（即该图最小完全同态的顶点数α值，也就是该图的色数γ）是否大于该图密度的1.5倍并向下取整的值 ，即看公式（1）α≤［1.5ω］和（2）公式γ≤［1.5ω］是否成立。

一条道路的密度是2，两条道路的联的密度就是4，联中的最大团则是K₄，两条道路的联的密度已经达到了平面图所有密度的最大值。由于联中的最大团只是图中的一个分子图，其中的顶点数一定不可能大于图中最大团的顶点数。所以可以说在密度小于等于3的任何平面图中都是不可能出现两条以上有联存在的不可同化道路的。如果有多条不可同化道路，也一定是不可能构成联的，也只相当于只有一条的情况，只可能有一个顶点同化不到最大团中去。其色数也只能是γ≤3＋1＝4的。

当ω＝1时，图中的最大团是K₁，只是一个顶点，图中没有任何边，当然也就不可能有任何的道路了，即有S＝0，则γ₁＝α₁＝ω＋S＝1＋0＝1≤ ＝1。

当ω＝时，图中的最大团是K₂，不可能有两条以上不可同化道路构成联的情况，只能是单条的，即有S＝1，则γ₂＝α₂＝ω＋S＝2＋1＝3≤ ＝ ＝3≤ ＝ ＝3。

当ω＝3时，图中的最大团是K₃，也不可能有两条以上不可同化道路构成联的情况，也只能是单条的，即有S＝1，则γ₃＝α₃＝ω＋S＝3＋1＝4≤ ＝ ＝4。

当ω＝4时，图中是否可以存在不可同化道路或者说是饱和道路呢，通过画图可以看出，密度为4 的平面图中是不可能存在不可同化道路和饱和道路的，如图4。证明如下。

图5是在一个完全图K4（密度是4）的外面增加一条不可同化道路或者是饱和道路时的图，图密度虽然还是4，但这种图就已经不再是平面图了，因为图中都已出现了交叉边。

图4中的这四个密度是4的图的最大团K4团外均有一条饱和道路，但只有上面两个图中的饱和道路又是不可同化道路，下面两个图中的饱和道路却不是不可同化道路。图中的饱和道路又是不可同化道路的两个图的最小完全同态的顶点数是4＋1＝5，着色时均得用5 种颜色，的确图4中上面两个图中也是用了红（1）、紫（2）、绿（3）、兰（4）、黑（5）五种颜色（图中K4团中的数字既是顶点序数，又是颜色序数；而PN道路中的数字，上面是顶点序数，下面是颜色序数。下同）；而图4中下面两个图中，饱和道路不是不可同化道路，这两个图的最小完全同态的顶点数则仍是4，着色时却都只用了红（1）、紫（2）、绿（3）、兰（4）4种颜色。但都很明显，这四个图都不是平面图，因为图中都有一条交叉边。

http://s9/mw690/61aec5afge0e8a87b0e38&690首先从图中有一条不可避免的交叉边e就可以看出其不是平面图了，另外还可以证明该图的边数的确是大于3V－6的，也能说明其不是平面图。

设这条饱和道路Pn的顶点数为n，则：①这条道路共有n－1条边，②其与最大团K4相邻的边数是（4－2）n＋2＝2n＋2条（其中每个顶点各与K4团的两个顶点（ω－2＝4－2＝2）相邻，两个端点顶点又各与K4团中的另一个顶点相邻），③K4团的边数是4×（4－1）/ 2＝6；④共计该系统的总边数是（n－1）＋（2n＋2）＋6＝3n＋7条；⑤这4＋n个顶点构成的图如果是平面图时，其边数最大只能是e≤3v－6≤3×（4＋n）－6＝3n＋6条，⑥而现在该图实际的边数却有3n＋7条，大于3n＋6。⑦所以密度为ω＝4的图中，如果在某一个K4团外，只要有一条道路是饱和道路时，则不管这条饱和道路是否是不可同化道路，这个图就都不是平面图了，而是一个非平面图。⑧所以说任何密度是4的平面图同化时的最小完全同态的顶点数或其顶点着色的色数都恒等于4。

从以上的检验中可以看出，任何平面图的最小完全同态的顶点数及色数都是小于等于其密度的1.5倍并向下取整值的，不会有任何反例。所以说公式（1）ω≤α≤［1.5ω］就是平面图同化时最小完全同态的顶点数的界。同样也因为γ＝α，所以也有ω≤γ≤［1.5ω］，

这就是上面的公式（2），也就是任意平面图顶点着色色数的界。也可以说是对四色猜测的一个证明。

3、四色猜测的证明

3、1  平面图四色猜测的证明

因为平面图的最小完全同态与色数有界都是ω≤α＝γ≤［1.5ω］，就可以把平面图的密度一个个的代入到其中进行检验，看平面图的每一个密度条件下，看当最小完全同态的顶点数或色数处于上界时，是否大于4。如果都不大于4，则猜测就是正确的，否则，猜测就是错误的。

当平面图的密度ω小于等于3时，α＝γ≤［1.5ω］≤4；而平面图的密度当ω＝4时，上面我们已经知道图中是不可能存在不可同化道路的。没有不可同化道路，就不存在不可同化到最大团中去的顶点，这样图的最小完全同态的顶点数一定仍是4，当然图着色时的色数也一定是4，也是不大于4的。以上可以看出任何一个平面图的最小完全同顶点数或色数都是不大于4的。这就证明了平面图的四色猜测是正确的。

3、2  地图四色猜测的证明

由于地图是一种叫做3—度正则的特殊平面图，因为地图中所有的顶点的度都是3,即每一个顶点均连着三条边。给地图的面上的着色就相当于给地图的对偶图的顶点着色。再由于平面图的对偶图仍是平面图，所以地图的对偶图也是平面图，且是一种叫做极大图的特殊平面图，因为地图的对偶图中的每一个面都是三边形面。上面我们已经证明了任何平面图顶点着色的色数都不大于4，那么地图的对偶图顶点着色的色数也就一定也不大于4。这也就使得地图的四色猜测得到了证明是正确的。

雷  明

二○一三年七月三日于长安