任意平面图的最小完全同态

雷明85639720

任意平面图的最小完全同态
——兼论四色猜测的证明
雷  明
（二○一三年七月三日）
我们在多次的研究中已经知道，对于密度为ω的图中的某一个最大团Kω来说，其外若有一条不可同化的道路时，则该图同化的最终结果（该图的最小完全同态）一定是一个Kω＋1的完全图，该图的色数就是γ＝ω＋1，并且也得到了相互可构成联的不可同化道路的条数S≤［ω/ 2］。
因为平面图的密度都不大于4，所以我们就可以对密度不大于4的平面图的密度一个个的进行验证，看该密度下的图中是否存在不可同化道路，可能的条数又是多少，图同化后的最小完全同态的顶点数是多少。把一个无穷的问题变成一个有穷的问题。只要各种密度的平面图的最小完全同态的顶点数都不大于4时，其顶点着色的色数也就不会大于4，猜测就是正确的，否则就是不正确的。
一条道路的密度是ω＝2，两条道路的联的密度就是ω联＝2ω＝2×2＝4，联中的最大团则是K4，两条道路的联的密度已经达到了平面图所有密度的最大值，所以说在密度ω≤3的平面图中，是不会出现两条不可同化道路构成联的情况的，如果有多条不可同化道路，一定是没有构成联的，只相当于一条时的情况。其色数也一定是γ≤3＋1＝4的。
当ω＝1时，图中的最大团是K1，只是一个顶点，图中没有任何边，当然也就不可能有任何的道路了，即有S＝0，则γ1＝α1＝ω＋S＝1＋0＝1≤ ＝1。
当ω＝时，图中的最大团是K2，不可能有两条以上不可同化道路构成联的情况，只能是单条的，即有S＝1，则γ2＝α2＝ω＋S＝2＋1＝3≤ ＝ ＝3≤ ＝ ＝3。
当ω＝3时，图中的最大团是K3，也不可能有两条以上不可同化道路构成联的情况，也只能是单条的，即有S＝1，则γ3＝α3＝ω＋S＝3＋1＝4≤ ＝ ＝4。
当ω＝4时，图中是否可以存在不可同化道路或者说是饱和道路呢，通过画图就可以看出，密度为4 的平面图中是不可能存在不可同化道路和饱和道路的，如图11。证明如下：
图11是在一个完全图K4（密度是4）的外面增加一条不可同化道路或者是饱和道路时的图，图密度虽然还是4，但这种图就已经不再是平面图了，因为图中已出现了交叉边。
图11中的这四个密度是4的图的最大团K4团外均有一条饱和道路，但只有两个图中的饱和道路又是不可同化道路。图中的饱和道路又是不可同化道路的两个图的最小完全同态的顶点数是4＋1＝5，着色时均得用5 种颜色，的确图中也用了红、兰、紫、绿、黑五种颜色；而图中的饱和道路不是不可同化道路的两个图的最小完全同态的顶点数则仍是4，着色时却都只用了红、兰、紫、绿4种颜色。但很明显，这四个图都不是平面图，因为图中都有一条交叉边。
首先从图中有一条不可避免的交叉边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。
从以上的检验中可以看出，任何密度的平面图的最小完全同态的顶点数都不大于4，当然，着色时的色数也是不会大于4 的。这也就证明了四色猜测是正确的。
雷  明
二○一三年七月三日于长安