[原创]四色猜测是不可逆的

雷明85639720

[watermark]

四色猜测是不可逆的
雷  明
（二○一三年元月九日）
网上许多的网友都对四色猜测进行了证明，我在《任意图着色色数的界》一文中也对猜测进行了证明，说明了任何平面图的色数都不大于4的结论是正确的。但这个结论却是不可逆的，也就是说色数不大于4 的图不一定都是平面图。例如K3,3图的色数是2，不大于4，但K3,3图却不是平面图，而是一个典型的非平面图。
我在《任意图着色色数的界》一文中对猜测进行证明时，说到了密度等于4的平面图的色数恒等于4，但我在该文中把证明省略了。从任意图的色数的界ω≤γ≤1.5ω（其中ω是图的密度，也即图中最大团的顶点数；γ是图的色数）中可以看出，密度是4的任意图的色数可能是4，5，或6，但当色数为5或6时，图本身就不再是平面图而是非平面图了。现在证明如下：
图的色数只所以能够比其密度值大，关键是图中某最大团外一定至少有一条不可同化道路（不可同化道路见《任意图着色色数的界》一文），该道路中一定有一个顶点是同化不到最大团中去的，这样图的最小完全同态的顶点数就一定比图的密度要大了。由于图的色数与其最小完全同态的顶点数是相等的，所以其色数也就比图的密度要大了。
在一个密度为ω＝4的图中，若有一个由最大团和该团外的一条不可同化道路组成的分子图，这个分子图本身也是一个图，其密度也是4，而其色数却是γ＝5。如图1中的两个图。另外图2 中的两个图也是密度为ω＝4的图，其中各虽有一条饱和道路，但因该道路中的各个顶点均可同化到最大团K4中去，因而其色数却是γ＝4。但可以看到该四个图中的共同特点是都有交叉边存在，所以这几个图都不是平面图，这是从对图形的观察中得出该四图是非平面图的结论。从理论上也可以证明这四个图不是平面图的结论的。


已知任何平面图的边数e一定是e≤3v－6的，只要能证明该四个图的边数是大于3v－6时，也就可以说明该四个图不是平面图。
已知：K4团的顶点数是4，其边数是6（6＝4×（4－1）/ 2）；
      PN道路的顶点数是n，其边数是n－1；
      PN道路与K4团相邻的边数是2n＋2（即道路中的每个顶点各有两条边与K4团顶点1和2相邻，道路的两个端点顶点又各与K4团的另外两个顶点相邻。
则以上四图的顶点数v都是：v＝4＋n；
如果以上四图都是平面图时，则其边数e一定是e≤3v－6＝3（4＋n）－6＝12＋3n－6＝6＋3n；
然而以上四图的实际边数却是e＝6＋n－1＋2n＋2＝7＋3n
实际的边数7＋3n＞6＋3n，而7＋3n－6＋3n＝1，正好是图中的那条交叉边，这就说明了以上四个图不是平面图而是非平面图了。
证毕。
通过以上的证明，进一步说明了四色猜测是不可逆的，即不是所有色数小于等于4 的图都一定是平面图。同时也进一步说明了不是所有密度为小于等于4 的图也都是平面图，说明平面图的密度一定小于等于4 也是不可逆的。

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

尚九天

下面引用由雷明85639720在 2013/01/09 08:58am 发表的内容：
(水印部分不能引用)
-=-=-=-=- 以下内容由 雷明85639720 在  时添加 -=-=-=-=-

                        四色猜测是不可逆的
                    ~~~~~~~~~~~~~~~~~~~~~~~~
                    ~~~~~~~~~~~~~~~~~~~~~~~~
雷  明
...

的的确确地不可逆！