[原创]我研究四色问题的五篇论文

雷明85639720

[watermark]
以下是我发给夏门大学杨卫华博士的关于我研究四色问题的五篇论文（图请见上面的DOC文件中，因为这里图发不上去）
我研究四色问题的五篇论文
雷  明
（二○一二年十二月二十日整理于长安）
      
1、不着色也是能够证明四色猜测的
   ——我解决四色问题的主导思想
2、任意图顶点着色色数的界
    ——四色猜测证明方法之一
3、赫渥特地图着色公式的由来
   ——四色猜测证明方法之二
4、5—轮构形是可约的
    ——四色猜测证明方法之三
5、四色猜测的一种简单证明方法
   ——四色猜测证明方法之四
二○一二年十二月二十日•长安修改
一、不着色也是能够证明四色猜测的
——我解决四色问题的主导思想
雷  明
（二○一二年五月六日，八月十二日、十二月十九日两次修改）
关键词：总体  共性  个体  个性  
摘  要：阐明了笔者不用着色的方法证明四色猜测的思路。
由于图的多样性，无限性，不可能把所有的图都画完，也不可能对所有的图都进行着色，所以就不可能用着色的方法对四色猜测进行证明。而只能走不画图，不着色的道路。本人解决四色问题的主导思想是：从图论入手，专门研究图的结构参数，找出图的着色数与图的某些结构参数之间的关系，从而对猜测进行了证明。
1、先从图的总体出发：
1、1  总体及图的共性
1、1、1  总体——任意图：包括平面图与非平面图。
1、1、2  图的共性——图的密度［1］：图中至少都有一个最大的团，该团的顶点数就是图的密度。
1、2  几个概念：
1、2、1  图顶点着色——给图中各顶点着以不同的颜色，使得相邻的顶点不用同一种颜色，但不相邻的顶点却不一定非得要用相同颜色。
1、2、2  顶独立集［2］划分——把图中各顶点分配到不同的集合内，使得相邻的顶点不在同一个集合里，但不相邻的顶点却不一定非得分配到同一个集合里去。
1、2、3  图的完全同态［3］——把不相邻的顶点凝结成一个顶点，使图最后变成一个完全图［4］，这个完全图就是图的完全同态。看来在求图的完全同态的过程中，是不能把相邻顶点凝结在一起的，但不相邻的顶点却不一定非得要凝结到一起。把不相邻的顶点凝结在一起的过程叫做“同化［5］”运算。
1、3  与以上概念对应的几种参数：
1、3、1  图的色数——图顶点顶点着色时所用的最少颜色数。
1、3、2  最小顶独立集数［6］——对图在进行顶独立集划分时所得到的最少的顶独立集的个数。
1、3、3  最小完全同态的顶点数［7］——在对图进行顶点同化时最终所得到的、顶点数最少的那个完全同态的顶点数。
1、4  几种参数的关系：
从以上几种概的定义可以看出，上面的几种参数应该是相等的，即有
图的色数＝最小顶独立集数＝最小完全同态的顶点数
最小完全同态中的每一个顶点，均代表着图中若干个不相邻的顶点，而不相邻的顶点在一起所构成的集合就是图的顶独立集。同一顶独立集内的顶点均是不相邻的，所以着同一颜色是符合要求的，那么最小完全同态有多少个顶点，该图的最小顶独立集数就是多少，一个顶独立集用一种颜色，有多少个顶独立集，该图着色时就得用多少种颜色，这就是图的色数。
1、5  求几种参数的方法：
1、5、1  求图的色数——着色法，但图的种类多种多样，一至无穷，是无法把所有的图都着色完的，即就是一个图，由于其顶点可以是无限多，也难以确定其色数是多少。
1、5、2  求最小顶独立集数——抽屉法，即把每个顶点向不同的抽屉里放置，使相邻的顶点不在同一个抽屉之内，同样也无法把所有图都分配完，同样也就是一个图，也是难以把其顶点分配完的。
1、5、3  求最小完全同态的顶点数——用“同化”的方法。所谓同化，就是把不相邻的顶点凝结在一起的过程，使其变成一个顶点。可以不用具体的图，只用一个能代表总体形象的、具有一般意义的图。理论上，任何图通过同化运算，最后都可以得到一个顶点数最少的完全同态，这就是图的最小完全同态。可以证明，任意图的最小完全同态的顶点数与图的密度的关系是：大于等于图的密度而小于等于图的密度的一倍半向下取整的值（这里的密度是指图中最大团的顶点数）。其证明方法请见下面的第二篇论文证明四色猜测的方法之一《任意图顶点着色色数的界》。
由于图的色数＝最小顶独立集数＝最小完全同态的顶点数，所以图的最小顶独立集数与色数也都是大于等于图的密度而小于等于图的密度的一倍半向下取整的值。这就是任意图的色数的界。
由于图的密度可以是无穷大的，所以对于任意的图来说，这也是一个无穷的问题。
2、 再到对个体图的检验：
2、1  个体——平面图，即亏格为0的图。这种图是能够嵌入到球面（或平面，其亏格也是0）上的图。
2、2  共性中的个性：由于平面图的密度都不大于4［8］，所以这就把一个对密度来说的无穷的问题变成了一个有穷的问题了。
2、3  把平面图的四种密度，一个个的代入到任意图的色数的界中去，就得到了任何平面图顶点着色时的色数总不大于4的结论。这也就证明了四色猜测是正确的。
参考文献：
［1］图的密度（Density of a），见《图论的例和反例》一书第213页，［美］M•卡波边柯与J•莫鲁卓合著，聂祖安翻译，湖南科学技术出版社出版，湖南省新华印刷二厂印刷，1988年4月第1版第一次印刷。
［2］顶独立集（也叫稳固集，stability set），见《图论导引》一书第280页和第411页，李修睦著，华中工学院出版社出版发行，武汉大学出版社印刷总厂印刷，1982年12月第1版，1986年9月第2次印刷。顶独立集有的文献上又叫点独立集（Independent set of points），也可见聂祖安所译《图论的例和反例》一书第32页和第218页。
［3］完全同态（Complete homomorphism），见聂祖安所译《图论的例和反例》一书第17～18页和第211页。
［4］完全图（Complete graph），见聂祖安所译《图论的例和反例》一书第211页。
［5］同化，见聂祖安所译《图论的例和反例》一书第17～18页和第211页。“同化”有的文献上又叫“收缩”，我认为叫同化合适一些，因为它是把两个不相邻的顶点凝结到一起的过程，而收缩则是要沿着某一路线进行的过程，这一路线就是某条边，所以我认为只有把两个有边相邻的顶点凝结到一起的过程叫收缩也才是合适的。“收缩”一词也请参见《图论的例和反例》一书第214页的“初等收缩”（Elementary contraction）一词的注释。
［6］最小顶独立集数，这是我自已定义的一个专业名词。一个图能分划成若干个顶独立集，其中必有一个分划中的顶独立集个数是最少的，这就是最小顶独立集数。最小顶独立集数与图论中把某个顶独立集内的顶点数定义的“顶独立数”是不同的，而是与图的最小完全同态（见以下［6］中的最小完全同态）的顶点数是相等的。
［7］最小完全同态的顶点数，这也是我自已定义的一个专业名词。一个图通过同化运算可得到不同的完全同态，其中顶点数最少的一个就是最小完全同态，其顶点数就是最小完全同态的顶点数。
［8］平面图的密度都不大于4，这是已经证明了的事实，所有的文献中都有这样的结论。
雷  明
二○一二年十二月二十日于长安
   
注：该文已于二○一二年五月九日在《数学中国》网上发表。
二、任意图顶点着色色数的界
——四色猜测证明方法之一
雷  明
（二○一二年六月十七日，八月十二日、十二月十九日两次修改）
关键词：图  着色  顶独立集  完全同态  同化  四色猜测
摘  要：不对任何图进行着色，可以证明四色猜测是正确的。
1、几个概念
1、1  图是由顶点与某些顶点间的连线（边）所构成的集合。有边相连的两顶点叫相邻顶点。
1、2  图顶点的着色：给图的顶点着以不同的颜色，使得相邻的顶点不着同一颜色。这里的关键是相邻顶点不能着同一颜色。图中所用的最少颜色数叫做该图顶点着色的色数，用γ表示。
1、3  顶独立集［2］划分：把图中的顶点划分到不同的集合内，使得相邻的顶点不被划分到同一个顶独立集内。这里的关键也是相邻的顶点不能划分在同一个独立集内。一个图所能划分出的最少的顶独立集的个数，叫做该图的最小顶独立集数［6］，用β表示。注意，这里的“顶独立集数”是顶独立集的个数，不同于图论中用某顶独立集内的顶点数所定义的“顶独立数”。
1、4  图的同化［5］运算：把图中不相邻的顶点，凝结为一个顶点的过程叫图顶点的同化。这里的关键也是相邻顶点不能同化到一起去。每同化一次所得到的图，叫做图的一个同态［9］，一个图经过若干次同化后，最终得到的结果一定是一个完全图［4］，这叫做图的完全同态［3］。其中顶点数最少的那一个完全同态就叫某图的最小完全同态［7］。最小完全同态的顶点数用α表示。
1、5  从以上的几个概念可以看出：
图顶点着色的色数γ
＝图的最小顶独立集数β
＝图的最小完全同态Kα的顶点数α
最小完全同态中的每一个顶点均代表着图中若干个不相邻的顶点，而不相邻的顶点在一起所构成的集合就是图的顶独立集。同一顶独立集内的顶点均是不相邻的，所以着同一颜色是符合要求的，那么最小完全同态有多少个顶点，该图的最小顶独立集数就是多少，一个顶独立集内的所有顶点只用一种颜色，有多少个顶独立集，该图着色时就得用多少种颜色，这就是图的色数。
由于图中的最大团Kω中的各个顶点均是两两相邻的，不可能再进行同化，所以最小完全同态的顶点数α一定不会小于图的密度［1］ω（图的密度就是图中最大团Kω的顶点数），所以又有
γ＝β＝α≥ω                          （1）
这就是任意图顶点着色色数的下界。
2、任意图顶点着色色数的界
请看下面两个图的同化过程。这两个图都不是具体的图。图中最大团Kω外的一条道路［10］Pn的每一个顶点都与最大团Kω中未画出的那ω－2个顶点相邻（相邻的边在图中也未画出），道路的两个端点顶点又与最大团中剩余的那个K2团的两个顶点相邻。若在这条道路与最大团间再任增加一条边，将会导致图的密度发生变化（或者道路就会变成两条具有上述性质的道路，道路的长度也就会变短），所以把这样的道路就叫做“饱和道路”。

图1中，在饱和道路Pn中，当n为奇数时，Pn中总有一个顶点同化不到最大团Kω中去，且Pn中的每一个顶点都可成为这样的不可同化顶点；否则，当n为偶数时，Pn中的所有顶点都可以全部同化到最大团Kω中去。
图2 中，则是在饱和道路Pn中，当n为偶数时，Pn中也总有一个顶点同化不到最大团Kω中去，同样的，Pn中的每一个顶点也都可成为这样的不可同化顶点；否则，当n为奇数时，Pn中的所有顶点也都可以全部同化到最大团Kω中去。
由此可以从道路与最大团的相邻关系方面对道路进行分类如下：
1、非饱和道路，上面已经证明了有一部分的饱和道路上的所有顶点，都可以全部同化到最大团中去，那么非饱和道路中的所有顶点也都一定是可以同化到最大团中去；
    2、饱和道路，在道路与某一最大团间增加任一条边时，图的密度就会增大，或者路道就会变成两条较短的饱和道路。以上图1和图2 中的道路就是饱和道路。该类道路又可分为两类：
1、可同化道路，这种道路中的各个顶点都是可以同化到最大团中去的；
2、不可同化道路，这种道路上总有一个顶点同化不到最大团中去。
还可以证明，当不可同化道路是回路（圈）时，同样也有与以上图1和图2的两种情况完全相同的结论。同样也可以证明当图1和图2中的Pn是或非饱和道路时，Pn中的所有顶点也都是一定能够同化到最大团中去的。
如果有S条不可同化道路，且这S条道路构成了联［11］时,就有S个顶点同化不到最大团中去，这S个顶点因其本来在联中就是相邻的，不可再同化在一起，所以就有图的最小完全同态Kα的顶点数是
α＝ω＋S                                     （2）
请注意，如果各条道路间均没有构成联，则这S个不可同化的顶点因其本来就不相邻还可同化成一个顶点，所以不可同化道路的条数再多，只要没有构成联，仍相当于只有一条不可同化道路的情况，仍然只有一个顶点同化不到最大团中去。
还要注意的是，真正在进行同化时，由于不可同化道路中的各个顶点都可以作为不可同化到最大团中去的顶点，所以要把各条不可同化道路间互不相邻的顶点留作这样的不可同化顶点，最后再把它们同化成一个顶点，以求出某图正确的最小完全同态。
由于联的密度［12］是构成联的各个分子图的密度的和，又因为道路的密度是2,所以该联的密度是就2S。这个联又只是图的一个分子图，其密度一定不会大于图的密度，所以又有2S≤ω,即S≤ω/2。又因为不可同化道路的条数S必须是整数，所以对S还要向下取整，即又有
       S≤                                     （3）
因此就有图的最小完全同态的顶点数的界是：
ω≤α≤ω＋S＝                        （4）
因此又有
ω≤γ＝β＝α≤                       （5）
γ＝β＝α≤ 就是任意图顶点着色色数的上界。因此又有任意图顶点着色色数的界是
ω≤γ≤                               （6）
3、四色猜测的证明
3、1  平面图四色猜测的证明
由于平面图的密度都不大于4［8］，所以这就使得公式（6）ω≤γ≤ 对于图的密度ω来说的无穷问题就变成了一个有穷的问题了。
把平面图的密度从1到4一个个的代入到以上的任意图顶点着色色数的界中，就可得到任何平面图的色数都不会大于4，即有
            γ平面图≤4                                  （7）
当图的密度是4时，从公式（6）中可以看出，其色数有可能是4，5，6三种可能，但当色数大于4时，尽管图的密度还是4，但这种图就已经不再是平面图了，因为图中已出现了交叉边（证明略）。
奇圈［13］中的每一个K2团外都有一条不可同化道路，所以圈［14］的密度虽是2，但奇圈的色数却是3，等于ω＋1；同样的，奇轮［15］中的每一个K3团外也都有一条不可同化道路，所以轮［16］的密度虽是3，但奇轮的色数却是4，也等于ω＋1。
由此可以得出：含有奇轮的平面图的色数一定是4，密度为4的含有K4团（3—轮，是奇轮）的图也是属于含奇轮的图；不含奇轮但含有偶轮［17］的图的色数则是3。不含轮而含有奇圈的平面图的数色一定是3，密度为3的含有K3团（3—圈，是奇圈）的图也是属于含奇圈的图；不含奇轮与奇圈但含有偶圈［18］的图的色数则是2,不含轮和圈而只含有 树［19］的图的色数也是2。不含轮和圈和树的图全是孤立顶点，1种颜色就够用了。
这就证明了平面图的四色猜测是正确的。
3、2  地图四色猜测的证明
地图也是一种平面图（是特殊的3—正则平面图，各顶点的度均是3），给其面上的染色就相当于给其对偶图［20］（也是一种特殊的极大平面图,各面均是3—边形面）的顶点着色。由于平面图的对偶图仍是平面图［21］，又因为平面图的顶点着色四种颜色够用了，所以地图染色时四种颜色也就够用了。
这也就证明了地图染色的四色猜测也是正确的。
4、图值函数［22］顶点着色色数的界
有了任意图顶点着色色数的界，研究图的线色数［23］、全色数［24］以及图的任何图值函数的色数就方便得多了。
比如线图［25］的密度等于原图中的最大度Δ，所以图的线色数就是其线图顶点着色的色数，其界是
            Δ≤γ线≤                              （8）
这就是1964年V•G•Vizing给出的线色数的界［26］，但公式（8）比其更加完善。当时V•G•Vizing给出的线色数的界是Δ≤γ线≤Δ＋1,且只有在Δ等于2和3 时才是正确的。
又比如全图［27］的密度等于原图中的最大度Δ加1,所以图的全色数就是其全图顶点着色的色数，其界是
Δ＋1≤γ全≤                       （9）
这也就是1965年Behzad提出的全色数的猜想［28］，同样公式（9）也比其更加完善。当时Behzad提出的全色数的猜想是Δ＋1≤γ全≤Δ＋2，也只是在Δ等于2 和3时才是正确的。
若给一个图G,其图值函数为f（G），f（G）的密度［29］ωf（G）是与图G的有关参数有关的函数（如ω线＝Δ原图等），则图值函数f（G）的顶点着色色数［30］的界是
        ωf（G）≤γf（G）≤                     （10）
以上的线图和全图都是原图的图值函数，其色数（也就是原图的线色数和全色数）就是这样得来的。
由于平面图的对偶图也是原图的图值函数，给平面图的面上的着色就相当于对其对偶图的顶点着色，因其对偶图仍是一个平面图，所以平面图（原图）的面色数也是
γ平面图面色数≤4                                  （11）
地图着色也是给平面图（地图本身就是一个3—正则的平面图）的面的着色，所以这也就证明了地图的四色猜测也是正确的。
5、结论：四色猜测是正确的
本文没有对任何一个具体的图着色，只从图的色数等于图的最小完全同态的顶点数着手，得出了最小完全同态的顶点数与图的密度间的关系，进而得到任意图顶点着色色数的界，把平面图的密度不大于4的特点代入其中，就得到了任何平面图着色的色数都不大于4的结论，从而也就证明了四色猜测是正确的。
参考文件：
［9］同态（Homomorphism），见聂祖安所译《图论的例和反例》一书第217～18页、第146～147页和第217页。
［10］道路（Path），见聂祖安所译《图论的例和反例》一书第224页。
［11］联，也就是两个图的和（Sum of two graphs）, 见聂祖安所译《图论的例和反例》一书第77～78页和第228页。
［12］联的密度，两个图的联也是一个图，所以也一定有其最大团，也就有其密度。若一个图的密度是ω1，另一个图的密度是ω2，可以证明这两个图的联的密度ω联＝ω1＋ω2，若有S个图，两两间都有联存在时，也可以证明该联的密度是ω联＝ 。这是我自已得出的结论。
［13］奇圈，顶点数是奇数的圈。
［14］圈（Cycie），见聂祖安所译《图论的例和反例》一书第212页。
［15］奇轮，即轮沿顶点是奇数的轮，与偶阶轮等价，总顶点数偶数。
［16］轮（Wheel）也叫轮形图、轮状图。见聂祖安所译《图论的例和反例》一书第229页和李建中所译《图论导引》一书的第438页。
［17］偶轮，即轮沿顶点是偶数的轮，与奇阶轮等价，总顶点数奇数。
［18］偶圈，顶点数是偶数的圈。
［19］树（Tree），见聂祖安所译《图论的例和反例》一书第229页.
［20］对偶图（dual of a graph），见李修睦著《图论导引》一书第78页和第410页，
［21］平面图的对偶图仍是平面图，这是已经证明了的事实，所有的文献中都有这样的结论。
［22］图值函数（Graph-valued function），见聂祖安所译《图论的例和反例》一书第59～77页和第216页。
［23］线色数（line chromatic number），见聂祖安所译《图论的例和反例》一书第15页和第220页。
［24］全色数（Total chromatic number），见聂祖安所译《图论的例和反例》一书第17页和第228页。
［25］线图（Line graph），见聂祖安所译《图论的例和反例》一书第59页和第220页。
［26］1964年V•G•Vizing给出的线色数的界，见聂祖安所译《图论的例和反例》一书第15页。
［27］全图（Total graph），见聂祖安所译《图论的例和反例》一书第69页和第228页。
［28］1965年Behzad提出的全色数的猜想，见聂祖安所译《图论的例和反例》一书第17页。
［29］图值函数的密度，是我自已定义的。图值函数也是图，也应有自已的最大团，必然有它的密度。
［30］图值函数顶点着色色数，也是我自已定义的。图值函数既是图，也就应有顶点着色的色数。
雷  明
二○一二年七月二十三日于长安
注：该文已于二○一二年六月十九日在《数学中国》网上发表过。
三、赫渥特地图着色公式的由来
——四色猜测证明方法之二
雷  明
（二○一二年六月二十日，八月十二日、十二月二十日两次修改）
关键词：赫渥特  着色  四色猜测
摘  要：从适合于亏格为0的多阶曲面上的欧拉公式直接推导出了赫渥特的地图着色公式，该公式在曲面的亏格为0 时的值是小于等于4的，这也就证明了四色猜测是正确的。
1、赫渥特一生研究四色问题共六十年，虽发表过许多优秀的论文，但却没有最终解决这一问题。虽然如此，但他却得出了一个比四色问题更高级的、更丰富多彩的适合于任意亏格［31］的多阶曲面上的地图着色公式γn≤ ［32］，也正是因为他认为自已没有解决亏格为n＝0时的平面（或球面）上的四色问题，所以他给他的公式后面附加了条件n＞0。
2、在现有所能看到的文献资料中，在提到该公式时，也都只是引用了一下，并没有说明这个公式是如何得来的。也正是因为公式后有了附加条件n＞0，所以就成了一些人认为的“尽管公式中当n＝0时公式的值γ≤4,也不能说明四色猜测是正确的”的理由。这个公式当时赫渥特是如何得来的，我们不得而知，但我坚信总是有其由来的，只是我们一般的人看不到而已。要把该公式的由来弄明白那就是研究数学史的专家们的事了。
3、我们虽然不知道赫渥特地图着色公式的由来，但我们可以通过适合于任意曲面的多阶曲面上的欧拉公式［33］推导出这一公式。
多阶曲面上的欧拉公式是v＋f－e＝2（1－n），其中的n是图的亏格，也是图所能嵌入的最小曲面的亏格，而v、f、e分别是曲面上图的顶点数、面数和边数。当亏格n＝0时，公式就成为v＋f－e＝2，这就是我们经常见到的平面图的欧拉公式。我们知道完全图Kv的边数是e＝ ［34］，且完全图中的任何两两顶点都是相邻的，所以e和f也有3f＝2e的关系，即f＝ 。
先把f＝ 代入多阶曲面上的欧拉公式v＋f－e＝2（1－n）中，并整理后得到
3v＝e＋6－6n
再把e＝ 代入到上式3v＝e＋6－6n中，整理后得到
        v2－7v＋12（1－n）＝0
这是一个关于完全图的顶点数v的一元二次方程式。解这个一元二次方程得
    v1＝
   v2＝
  由于在v2＝ 中，当n≥1时，v2＝ ≤0，而任何图的顶点数都是不会小于1的，v≤0显然是不符合题意的，所以舍去不要。则该一元二次方程也只有一个根v1＝ 。因为图的顶点数必须是整数，所以该根还得向下取整，得
   v＝
由于任何完全图的色数γ就等于其顶点数v，所以把v＝ 中的顶点数v换成某亏格下的色数γn，就得到
    γn＝
这只是完全图的色数γn与其亏格n之间的关系。由于在同亏格条件下，同顶点数的图中完全图的边数是最多的，顶点间的相邻关系也是最复杂的，当然其色数也一定是最多的，而同顶点数的任一非完全图的色数都是要小于完全图的色数的，所以还要把上式中的等号改换成不等号，则变成
    γn≤
这就是任意图顶点着色的色数与其亏格的关系，也就是我们在文章最开头所说的赫渥特在1890年得出的多阶曲面上的地图着色公式。
显然，在这个公式中，当亏格n＝0时，γn≤4，这就是平面（球面）上的四色猜测。同样，当亏格n＝1时，γn≤7，这是轮胎面（环面）上的色数；当亏格n＝2时，γn≤8，这是眼镜匡面（双环面）上的色数，等等等等。这显然比一个四色猜测要更显得丰富多彩。
4、为什么有些人却死报着赫渥特原来公式中的附加条件n＞0不放，而硬说该公式对于亏格为n＝0的平面（球面）不适用呢，可能是因为他们还在认为赫渥特的图是不可4—着色的，也可能是他们也没有看到过赫渥特地图着色公式最开始时的由来，还有可能是因为他们不会从多阶曲面上的欧拉公式直接推导出赫渥特的地图着色公式的原因吧。
参考文献：
［31］亏格（Genus），见聂祖安所译《图论的例和反例》一书第9页和第216页，图的亏格是其可嵌入的曲面的最小亏格。而曲面的亏格则是“焊”在球面上的“环柄”的个数（见许寿椿著《图说四色问题》一书的第13页中的“高阶曲面（有一个或多个环柄的球）”，范益政所译《图论导引》一书的第214页，李建中所译《图论导引》一书的第212页），也可说是在球面上挖出的孔洞的个数。
［32］赫渥特（Heawood）多阶曲面上的地图着色公式γn≤ ，见聂祖安所译《图论的例和反例》一书第9页，许寿椿著《图说四色问题》一书的第11页，范益政所译《图论导引》一书第257～259页，李建中所译《图论导引》一书的第214页.
［33］多阶曲面上的欧拉公式，见范益政所译《图论导引》一书的第218～219页。
［34］完全图Kv的边数是e＝ ，其中V是顶点数，这在所有的文献中都有。
雷  明
二○一二年十二月二十日于长安
    注：此文已于二○一二年六月二十日在《数学中国》网上发表过。
四、5—轮构形是可约的
——四色猜测证明方法之三
雷  明
（二○一二年六月二十日，八月十二日、十二月二十日两次修改）
关键词：图  四色猜测  构形  不可避免  可约的
摘  要：仍然使用坎泊的颜色交换技术，证明了5—轮构形是可约的，从而再次证明了四色猜测是正确的。
由于任何平面图中至少有一个顶点的度是小于等于5［35］的，所以平面图的不可避免集中只可能有6种元素，即0—轮（即K1图），1—轮（即K2图）,2—轮（即2—重K3图），3—轮（即K4图）,4—轮和5—轮六种构形［36］。
这六种构形中，0—轮构形的色数是1, 1—轮构形的色数是2, 2—轮构形的色数是3, 3—轮构形的色数是4，都是小于等于4的，这几种构形都是可约的；4—轮构形坎泊早已证明是可约的；而5—轮构形，坎泊在未把各种情况都考虑周全的情况下，就根据前面证明的4—轮构形是可约的而认为5—轮构形也是可约的。在这种情况下他就认为自已证明了四色猜测是正确的，并且宣布了他的证明［37］。
可是在十一年之后，赫渥特构造了一个图，其中就有一个5—轮的中心顶点未着上其他顶点所用过的四种颜色之一，认为该图是不可约的。当时坎泊同样也不能将其中未着色的顶点着上赫渥特已用过的四种颜色之一［38］。直到现在已有一百五十多年了，整个数学界还认为5—轮构形仍然是不可约的。赫渥特的图真是不能4—着色吗，5—轮构形真是不可约的吗，不是的。现在就证明如下。
1、按赫渥特着色时所用的颜色交换的方法继续交换下去，然后再进行别的链［39］的交换后，仍是可以对赫渥特构造的图进行4—着色的，我早已于一九九二年三月八日在西安空军工程学院（今西安空军工程大学）召开的陕西省数学会第七次代表大会暨学术交流会上作过关于赫渥特图4—着色的学术论文报告（在报告完后，当时我就提出了不能以为赫渥特图一个图能够4—着色就认为四色猜测就得到了证明，因为图的种类的多样性、无限性，不可能把所有的图都着色完，即就是一个图，也可能因其顶点数的数量之大也不可能着完，所以用着色的方法是不能最终证明四色猜测的，正象阿贝尔用电子计算机花去了1200多个机器小时，对将近两千个平面图进行了验证，每个图所用的颜色数都没有超过四种，但也不能说明四色猜测被证明是正确的是同样的道理。），国内外也已有不少的人也都进行过这一工作，如中央民族大学的数学教授许寿椿教授，广东深圳市老年科协的董德华高级工程师，山西盂县党校的数学高级讲师张彧典老师，网名叫“一棵小草”和“平常心”的两位朋友等等，还有英国牛津大学的弗雷德•霍罗伊德和罗伯特•格兰丁•米勒等，这一切都的确说明了赫渥特的图是可以4—着色的。目前在数学界，可能再也没有人认为赫渥特的图是不可4—着色的了（以前大家都说赫渥特的图不是不可4—着色，甚至认为赫渥特对他的图也能4—着色，但却从未看到过那一个文献上有关于赫渥特图4—着色的实例）。
2、把赫渥特图中的关键顶点留下，而把其它的顶点去掉，就得到一个9点形，这就是一个5—轮构形，如图1。
由于图1中的b—g链和b—y链是在顶点2 和顶点8相交了两次的连通链，交换两次关于r的链r—g和r—y是不可能同时移去两个r的，即v也是不能着上图中已用过的r色的。如何办，只能想办法首先把连通的链变成不连通或者把交叉的链变成不交叉的。然后想办法移去5—轮周围只用过一次的一种颜色给v着上。

3、可以看出，对图1从b—g链和b—y链的交叉点顶点8（或顶点2）进行b—r链的交换后，既可做到使两链变得不连通，又可使两链变得不相交（如图2）,然后再任意进行一次关于非r链（或非b链）的交换，即可空出图中已用过的四种颜色之一给v着上。5—轮构形是可约的。
4、对于赫渥特的图，按照上面2、3两步的方法去做，立即可使赫渥特图中的未着色顶点着上赫渥特已用过的四种颜色之一。赫渥特图也是4—可着色的。
5、现在已经证明了平面图的6种不可避免构形都是可约的，那么平面图的四色猜测也就得到了明是正确的。
6、地图是一种3—正则（各顶点的度均是3）的平面图，给地图面上的着色就是给其对偶图的顶点着色，因其对偶图也是一种极大（各个面均是3—边形面）的平面图，所以任何地图的色数也一定是小于等于4的。这也就证明了地图四色猜测是正确的。
7、平面图的不可避免构型只有六种，这是人所共知的，因为任何平面图中不可避免的都会至少存在一个顶点的度是小于等于5的。1976年阿贝尔的验证，却避开了5—轮构形，用了一个什么叫双5—轮的所谓的“构形”来替代［40］，这分明还是没有证明5—轮构形道底是否是可约的嘛。所谓的双5—轮构形实际上就是图1中的那种构形，张彧典在他的文章《与〈阿贝尔—哈根证明四色定理〉商榷》一文中也指出了这一点。当给双5—轮构形中的一个未着色顶点着上颜色后，这不还是一个5—轮构形嘛。既然阿贝尔验证了双5—轮构形是可约的，那不也等于说5—轮构形也是可约的了吗，难道你不是一个顶点一个顶点的着色吗，你能一次同时给两个顶点着色吗。本来已经验证了5—轮是可约的，但就是不敢承认那就是对5—轮构形的着色，这不是怪事吗。阿贝尔用了将近两千个构形，再多一些又有什么用呢，难道就因为你着色的图越多就能说明你证明了四猜是正确的吗。这是一种穷举的笨办法。是对计算机资源的极大浪费。坎泊和赫渥特等前人没有证明5—轮构形是否可约，现在我们就想办法直接去证明它就行了，可阿贝尔却硬是要避开它，绕开矛盾走，无穷的在穷举，这是不科学的态度。为什么你不再多举一些呢，用三千个、五千个以至更多的图呢，你能举完吗。本来是一个有穷的问题，却被人为的硬要把它变成一个无穷的问题了。
参考文献：
［35］平面图中至少有一个顶点的度是小于等于5，这已是大家熟悉的结论，所有文献上都有这一结论。
［36］平面图的不可避免集中只可能有6种元素，见王树禾著《图论》一书第97页，科学出版社出版，新蕾印刷厂印刷，2004年1月第1版，2007年6月第四次印刷。
［37］4—轮构形坎泊（Kempe）早已证明是可约的；而5—轮构形，坎泊在未把各种情况都考虑周全的情况下，就根据前面证明的4—轮构形是可约的而认为5—轮构形也是可约的。在这种情况下他就认为并宣布了他证明了四色猜测是正确的。见范益政所译《图论导引》一书的第232页。
［38］当时坎泊也不能将其中未着色的顶点着上赫渥特已用过的四种颜色之一。见范益政所译《图论导引》一书的第233页。
［39］链，也叫坎泊链，是一条由两种颜色交替着色的道路。大家都很熟悉的图论专业术语（一下子找不到出处了，但我的定义绝对没错）。
［40］1976年阿贝尔的验证，却避开了5—轮构形，用了一个什么叫双5—轮的所谓的“构形”来替代。见王树禾著《图论》一书第98～100页。
雷  明
二○一二年七月二十三日于长安
注：此文已于二○一二年六月二十日在《数学中国》网上发表过。
五、四色猜测的一种简单证明方法
——四色猜测证明方法之四
雷  明
（二○一二年九月一日，十二月二十日修改）
任何平面图中都不会含有五个以上顶点互相相邻（有人叫全相邻）的情况［41］，以及任何平面图的密度都不大于4，即任何平面图中的最大团只可能是K4团，也即最大团的顶点数最多只可能是4，这都是图论里早已经过证明是正确的东西了。与这一结论相应的是地图（也是平面图）中不存在五个区域（或面）两两均相邻的情况。
由于这一原因，就决定了任何平面图中的某个最大团K4团以外的所有顶点至少与该最大团里有一个以上的顶点不相邻，这也就说明该最大团以外的任何顶点一定都是可以同化（不相邻的顶点凝结在一起的过程叫同化）到该最大团中来的，使得图最终可以变成一个完全图K4。这是一种情况；
二一种情况是，平面图中也有不含K4团的，其最大团的顶点数都小于4，也即其密度（把图中最大团的顶点数叫图的密度）是小于4 的。这些图同化的最终结果是不是一定都是一个顶点数小于等于4的完全图呢。可以肯定的回答：是。
任何平面图中的任何顶点都是处在一个轮的中心顶点位置上的，偶轮同化的结果是一个K3团，而奇轮同化的结果则是一个K4团，这时图中也就有了K4团，再继续同化下去，最终也一定会得到一个完全图K4。所以只要是含有奇轮的平面图，同化的最终结果一定是一个K4完全图；而不含奇轮的平面图同化的最终结果则一定是一个完全图K3。所以含有轮的图同化最后所得到的完全图的顶点数都是小于等于4的。
不含轮而只含圈的平面图中，偶圈同化的结果是一个K2团，而奇圈同化的结果则是一个K3团，这种图最终同化的结果也一定是顶点数小于4的完全图。只含有树的图（一定是平面图）同化的结果只可能是一个完全图K2；所有顶点均不相邻的繁星图［42］同化的结果只能是完全图K1。所以说不含奇轮（密度是4的平面图中必含有K4团，K4团本身也是一个奇轮，即3—轮）的图，同化的最终结果的顶点数也都是小于4的。
综合上述，说明了任何平面图同化的最终结果都一定是一个顶点数小于等于4 的完全图Kn(n≤4), 由于完全图各顶点都是互相相邻的，所以完全图有几个顶点着色时就得用几种颜色，K4的顶点数是4，当然完全K4着色时四种颜色一定就够用了，顶点数小于4 的完全图着色时色数也一定是小于4 的。
任何平面图同化后的最终结果的每一个顶点都是由若干个互不相邻的顶点同化而来的，这些顶点着上同一颜色是完全符合着色要求的。所以把平面图同化后得到的完全图着色后，把各个顶点连同已着上的颜色，按同化的相反方向又返回到其在原图中的位置时，这个图就已经着色完毕。由于任何平面图同化的最终结果都不会用到多于4 种的颜色，所以任何平面图着色时，其色数也一定是不会多于四种的，这就使猜测得到了证明是正确的。
参考文献：
［41］平面图中都不会含有五个以上顶点互相相邻（有人叫全相邻）的情况。这已是大家熟悉的结论，所有文献上都有这一结论。
［42］繁星图，这是我自已定义的专业名词。意思是若干个互不相邻的顶点，象天上的繁星一样。

雷  明
二○一二年十二月二十日于长安
注：该文已于二○一二年九月二日在《数学中国》网上发表过。
雷  明
二○一二年十二月二十日整理于长安
注：此文已于二○一二年八月十四日在《数学中国》网上发表过。