4—CC的又一简便证明方法

雷明85639720

4—C C的又一简便证明方法
雷  明
（二○一三年六月二十三日）
大家知道一个n色图一定可以通过同化运算最终成为一个完全图Kn，那么我们可以看一看任何一个平面图通过同化后所得到的完全图Kn的顶点数n最大是多少呢。由于平面图中的最大团Kω的顶点数是小于等于4 的，即平面图的密度是小于等于4 的，所以只要能说明任意平面图同化的最终结果是一个顶点数n≤4的完全图，猜测就是正确的，否则就是不正确的。
按我的同化理论，图中的最大团外只要有一条不可同化道路，这条道路中就有一个顶点同化不到最大团中去。现在我们就来看看各种密度条件下的平面图是否存在这种不可同化道路，同化后的最终结果是一个顶点数n为多大的完全图Kn就可以了。
1、ω＝1时，图中只有一个顶点而没有边，不可能有什么道路存在；
2、ω＝2时，复杂一点的图只能是带有圈的图，当圈是大于3的奇圈时，圈中的任一个K2团外所剩的属于圈中的顶点与边就构成了这个K2团的一条不可同化道路，一定有一个顶点同化不到K2团中去，图最终同化的结果一定是一个K3团,其顶点数n＝3＜4，该团仍是平面图。如图1，a；
3、ω＝3时，复杂一点的图只能是带有轮的图，当轮是大于3的奇轮时，轮中的任一个K3团外所剩的属于轮中的顶点与边就构成了这个K3团的一条不可同化道路，一定有一个顶点同化不到K3团中去，图最终同化的结果一定是一个K4团,其顶点数n＝4≯4，该团也是平面图。如图1，b；

由于两条道路的联的密度是2×2＝4，所以在ω＝2和ω＝3时，是不会出现有两条不可同化道路构成联的情况的，即就是一般的道路也不会出现两条道路的联的。

4、ω＝4时，两条道路的联的密度虽是2×2＝4≯ω＝4，但在ω＝4的图中，如果在K4团外有一条不可同化道路（或是饱和道路）时，图就不是平面图了。如图2。这几个图中显然都出现了交叉边，显然不是平面图。
其不是平面图还可以这样来证明：
设这条不可同化道路（或饱和道路）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的平面图中是不会存在饱和道路的，更不会存在不可同化道路的，同化的最终结果一定是一个完全图K4，其顶点数n＝4≯4。如果一个ω＝4的图同化的最终结果是一个K5图，该图一定不是平面图。
从以上证明可以得到结论，任何平面图同化的最终结果一定是一个顶点数不大于4 的完全图。这也就证明了任何平面图的色数都是不会大于4 的。四色猜测得到了证明是正确的。
雷  明
二○一三年六月二十三日于长安