四色猜测证明方法汇编（一）（共十三种方法，本贴为第1——第5种）

雷明85639720

四色猜测证明方法汇编（一）
雷  明
（二○一六年十一月五日）

目     录

1、平面图最小完全同态的顶点数是不大于4的
          ——四色猜测证明方法之一                     （3）
2、任何地图都是可3—边着色的
    ——四色猜测证明方法之二                      （8）
3、平面（球面）上可嵌入完全图的顶点数不大于4
    ——四色猜测证明方法之三                     （15）
4、平面（球面）上是不存在五色地图的
    ——四色猜测证明方法之四                     （18）
5、反证法证明平面上不存在五色地图
    ——四色猜测证明方法之五                     （21）
（以上在贴一）
6、平面图最小完全同态的亏格仍然是0
——四色猜测证明方法之六                     （22）
7、Mycielski—操作与平面图的色数
——四色猜测证明方法之七                     （26）
8、5—轮构形是可约的
——四色猜测证明方法之八                     （31）
（以上在贴二）
9、数学归纳法证明四色猜测
——四色猜测证明方法之九                     （37）
10、哈德维格尔猜测想是正确的
——四色猜测证明方法之十                     （40）
11、用还原法证明四色猜测
——四色猜测证明方法之十一                   （42）
12、用断链法证明四色猜测
——四色猜测证明方法之十二                   （44）
13、赫渥特的地图着色公式是正确的
——四色猜测证明方法之十三                   （46）
（以上在贴三）

平面图最小完全同态的顶点数是不大于4的
——四色猜测证明方法之一
雷  明
（二○一六年十月二十九日）

1、哈德维格尔猜想与哈拉里的结论
哈德维格尔猜想是：色数为n的图，最终可以同化（也即收缩。把图中不相邻的顶点凝结在一起的过程叫同化）为一个完全图Kn。这很容易证明，因为相同颜色的顶点一定是不相邻的，他们是可以同化为一个顶点的，所以同化的结果——完全图Kn——中一定有n个顶点；Kn中n个顶点均相邻是因为这n个顶点中，每一个顶点代表的是若干个在原图中不相邻、但又是着有相同颜色的顶点，且其中至少有一个顶点是与这个完全图Kn中的其他顶点是相邻的。
哈拉里也说过，图的色数等于图的最小完全同态的顶点数。把图中不相邻的顶点同化一次所得到的图就叫原图的一个同态；经过一系列的同化后，就会得到一个完全图，这就是原图的完全同态；在不同的完全同态中，顶点数最少的一个，就是原图的最小完全同态。
哈拉里与哈德维格尔是从同一回事的两个不同的方向说起的。哈德维格尔说的是把色数为n的、着色好色的图，经同化后最终可得到一个完全图Kn；而哈拉里则说的是把图进行同化，最后一定会得到一个顶点数最少的最小完全同态Kn，其顶点数n也就是图的色数。
可以看出，我们只要能证明平面图的最小完全同态的顶点数是不大于4的，就可使四色猜测得到证明是正确的。
2、任意图的最小完全同态的顶点数
任何图都有一个最大团，最大团的顶点数就是图的密度。现在我们首先看图中有没有不可同化到最大团中去的顶点。
设最大团是Kn，若其外有一条道路Pn，该道路的每一个顶点均与最大团中Kn相同的n－2个顶点相邻，道路的两个端点顶点又分别与最大团Kn中的其他两个顶点之一相邻，如图1（为了使图面清晰，图中最大团Kn中的那个Kn－2团与道路Pn中各顶点间的相邻关系均未画出）。按给出的条件，道路Pn中的任何顶点都是不可能同化到最大团Kn中的那个Kn－2团中去，而只能向剩下的那个K2团中去同化。这就把一条道路Pn向最大团Kn的同化转变成了向K2团的同化问题了。

在图1，a中，当道路的顶数n为奇数（或在图1，b中，当道路的顶点数n为偶数）时，道路Pn中总有一个顶点同化不到最大团Kn中的那个K2团中去，也即同化不到最大团Kn中去。把这样的顶点叫不可同化顶点。可见道路Pn中各顶点的不可同化的机会是相等的，即每一个顶点都可以作为这样的不可同化顶点。这时图的最大团就由原来的Kn变成了Kn＋1，图同化的最后结果就是一个Kn＋1完全图，这就是原图的最小完全同态，其顶点数n＋1就是图的色数。把这样的、总有一个顶点同化不到最大团中去的道路就叫不可同化道路。这时，图中的最大团就不再是原来的Kn而变成了Kn＋1，整个图中也就只有这一个Kn＋1团是最大的，当然其他的任何顶点也都一定是可以同化到这个最大的Kn＋1团中来的，所以说这个图的最小完全同就是Kn＋1团，顶点数是n＋1。
最大团外最多能有多少条不可同化道路呢？如果如果最大团外有S条不可同化道路，当各道路没有构成联时（联是一个图的所有顶点都和另一个图的任何顶点都相邻的图），各道路间总有不相邻的顶点存在，把这些顶点做为不可同化顶点是一定能够办到的。然后再把这S个不可同化顶点同化在一起，仍相当于只有一条不可同化道路的情况；如果这S条不可同化道路间已经构成了联时，则这S个不可同化顶点间，因其本身就是相邻的而不能再同化成一个顶点，就产生了S 个不可同化顶点。
这S条不可同化道路有没有上界呢？回答是，一定有。S条不可同化道路的联在图中也只是一个分子图，该分子图的密度2S（联的密度是构成联的各图的密度之和，道路的密度是2，所以S条道路的密度之和就是2S）是不会大于图的密度的，即是不会大于图的最大团的顶点数n的。所以有2S≤n和S≤n/2。可以看出，任意图的最小完全同态的顶点数是不会大于原图的最大团的顶点数的1.5倍的。
3、平面图的最小完全同态的顶点数不大于4
一个Kn团与其外一条不可同化道路Pn的总边数是：Kv团的边数有v（v－1）/2条，不可同化道路Pn的边数有n－1条，Kv团和Pn道路间的相邻边数有n（v－2）＋2条，三者的总边数和是v（v－1）/2＋n－1＋n（v－2）＋2＝v（v－1）/2＋n－1＋nv＋2n＋2＝v（v－1）/2＋3n＋1。
因为平面图的最大团是K4，最大密度也是4，当把v＝4代入上式v（v－1）/2＋3n＋1后得，K4团与一条不可同化道路Pn的总边数应是6＋3n＋1，而实际上在平面图的情况下，一个K4团与一条顶点数为n的道路Pn的总顶点数是4＋n，这4＋n个顶点的最大边数却是不会大于3（4＋n）－6＝12＋3n－6＝6＋3n的，显然前者6＋3n＋1是大于后者6＋3n的。这就说明了密度为4的平面图的最大团K4外是不可能有不可同化道路的，其最小完全同态的顶点数是不会大于4的。
对于密度小于4的平面图：当图密度是3时，最大团和不可同化道路的总边数应是4＋3n，K3团与Pn道路总共有3＋n个顶点，在平面图中最大只可能有9＋3n－6＝3＋3n条边，小于4＋3n；当图的密度是2时，最大团和不可同化道路的总边数应是2＋3n，K2团与Pn道路总共有2＋n个顶，在平面图中最大只可能有6＋3n－6＝3n条边，小于2＋3n；当图的密度是1时，最大团和不可同化道路的总边数应是1＋3n，K1团与Pn道路总共有1＋n个顶，在平面图中最大只可能有3＋3n－6＝3n－3条边，小于1＋3n；以上这些，都说明了在密度小于4的平面图中，最大团外是可以存在不可同化道路的，但最多只可能有一条（这个1均分别不大于其密度1，2和3的1.5倍），这是因为两条道路的联的密度是4（＝2×2），已不符合这里所说的密度小于4的平面图的条件了。这也就说明了密度小于4的平面图的最小完全同态的顶点数也是不会大于4的。
到此，已经证明了任何平面图的最小完全同态的顶点数都是不大于4的，也就证明了四色猜测是正确的。
3、平面图的（顶点）着色数的判定
密度为4的平面图，因其最小完全同态的顶点数总不会大于4，所以密度是4的平面图的色数只能是4（不大于4）；密度为3的平面图中若含有奇轮，而奇轮中有一条K3团的不可同化道路，所以密度是3的平面图的色数最大只能是4，否则色数则是3（均不大于4）；密度为2的平面图中若含有奇圈，而奇圈中有一条K2团的不可同化道路，所以密度是2的平面图的色数最大只能是3，否则色数则是2（也均不大于4）；密度为1的平面图K1，是一个孤立顶点，1种颜色就够用了（也不大于4）。

雷  明
二○一六年十月二十九日于长安

注：此文已于二○一六年十月三十日在《中国博士网》上发表过，网址是：


任何地图都是可3—边着色的
——四色猜测证明方法之二
雷  明
（二○一六年十二月二十九日）

1、泰特猜想的证明：
地图本身就是一个2—边连通的3—正则平面图。泰特曾经猜测想：2—边连通的3—正则平面图的可4—面着色（即地图四色猜测）等价于3—正则平面图的可3—边着色。这个猜想也是不难证明的。
3—正则平面图的特征——顶点数是偶数，边数是顶点数的1.5倍以及其是可3—边着色的，且三种颜色的边的数量也是相同的——同样也适用于地图。① 地图中的总度数是3v（v是地图中的“三界点”顶点数），每条边的两端各是1度，地图中e条边的总度数则是2e，即有3v＝2e的关系。这个公式不但说明了地图的边数是顶点数的1.5倍（即e＝3v/2＝1.5 v）；② 同时又说明了地图的顶点数一定是偶数，因为只有v是偶数时才能使边数e是整数，所以地图的顶点数一定是偶数。③ 地图的边数是e＝1.5 v，那么图中着色的边也就是1.5 v，每个顶点都连结着3种颜色的边，所以1.5 v/3＝0.5v，即着每种颜色的边都是0.5v条，三种颜色的边的条数是相等的。
若一个2—边连通的3—正则平面图是可3—边着色的，由于每个顶点都连结着三种颜色的边，则其任一种边2—色子图（若干条回路）一定是包含了图的所有顶点，该子图中的边和顶点不但相等而且都是偶数，剩下的该子图以外的相当于图的顶点数的一半数量的偶数条边，全是着第三种颜色的边。把某一种边2—色子图回路的两侧各个着以不同的颜色，则两种不同的边2—色子图叠加后，就可得到原来2—边连通的3—正则平面图。两种边2—色子图回路两侧的四种颜色叠加的结果，就象画家配制颜料一样，产生了四种新的颜色，分别着在原图中的各个面内，且两相邻的面具有不同的颜色。这就证明了泰特的猜想是正确的。同时，地图的可3—边着色等价于其可4—面着色也是正确的。

举一个简单的例子，正六面体图这个3—正则图的地图如图1。该图是可3—边着色的，也是可4—面着色的。最后着色只有三种颜色，是因为1—2—1边2—色子图中的a色没有与1—3—1边2—色子图中的b色相叠加，不可能产生第四种颜色，所以最后只用了三种颜色。
可以看出，欲证地图四色猜测是否正确，只要证明2—边连通3—正则平面图是否可以3—边着色的就可以了。
2、2—边连通3—正则平面图是可3—边着色的
① 3—正则平面图中的每个顶点都边有3条边，相关联的边不能用同一种颜色，所以其在边着色时，至少也要用三种颜色；② 又因为3—正则平面图中面的边数是任意的，所以若有一个面的边数是奇数时，该面的边着色最多也只要三种颜色也就够用了；③ 所以说3—正则的平面图是可3—边着色的。
3—正则平面图的可3—边着色，还可以这样来证明：① 由于图的边着色就是对其线图的顶点着色，而3—正则平面图的每个顶点（如图2，a中的a和b两顶点）所连结的3条边，在其线图中就都构成了一个3边形的面，是一个K3团，所以这个线图的密度就是3；② 又是由于3—正则平面图的每条边的两个端点顶点（如图2，a中的边a—b的端点a和b）共连结着4条边，在其线图中就表现为每个顶点均连结有4条边和4个顶点（如图2，a中的顶点0连结着1、2、3、4四个顶点），所以线3—正则平面图的线图是一个4—正则图。如图2，a。

① 因为3—正则平面图的线图的密度是3，所以其着色时至少就需要3种颜色；② 又由于该线图是4—正则的，每个顶点都连结着4个顶点，而以线图中每个顶点为中心时，最大只可能得到一个4—轮（如图2中的顶点1和2，3和4间均相邻时，比如正4—面体的线图（如图2，c）就是这样），4—轮着色只用3种颜色；③ 由于线图中的每个顶点又不可能处在一个完整的奇轮的中心（如图2，a中的顶点1和2，3和4间至少有一对不相邻时），所以该残轮着色时最多也不会超过3种颜色（奇轮的色数是4）；④ 综合以上的三种原因，可知该线图的色数一定是3，这也就证明了3—正则平面图是可3—边着色的结论是正确的。同时也就证明了任何地图都是可4—面着色的结论也是正确的，即地图四色猜测是正确的。
由于地图的每个顶点均连结着3种颜色的边，三种颜色的边数又都相同，都是顶点数的一半；所以图中由某两种颜色构成的边2—色子图一定包括了地图中的所有的顶点，并包括了图中三分之二的边数，剩余的三分之一的边就是着第三种颜色的边；第三种颜色的边的两个端点顶点都是上述边2—色子图中的顶点。
3、平面图的四色猜测也是正确的
因为2—边连通3—正则图（地图）是可4—面着色的，那么地图的对偶图——极大图——也就是可4—（顶点）着色的。而由任意的极大图经过减边或者去顶的办法，得到的任意平面图的色数只会是减少，而不可能再增大。所以也就证明了任意平面图也都是可4—（顶点）着色的，平面图的四色猜测也就得到了证明是正确的。
4、赫渥特地图的4—着色
图3到图7是赫渥特地图4—着色的各个步骤。图7是赫渥特地图可4—面着色的彩色地图。从赫渥特的可3—边着色，到它的可4—面着色，进一步验证了2—边连通3—正则平面图既是可3—边着色的，又是可4—面着色的。







雷  明
二○一六年十月二十九日于长安

注：此文已于二○一六年十月三十日在《中国博士网》上发表过，网址是：


平面（球面）上可嵌入完全图的顶点数不大于4
——四色猜测证明方法之三
雷  明
（二○一六年十月三十日）

1、多阶定向曲面上可嵌入最大完全图的顶点数
任何亏格的曲面上都存在一个不但可嵌入其中，顶点数最多的完全图Kv，且图中又不存在交叉边的情况，这就是可嵌入该亏格曲面上最大的（顶点数最多的）完全图。
已知顶点数v≥3的图都有3f≤2e（f是面数，e是边数）的关系，把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2（1－n）（n是图的亏格）得
    e≤3v－6（1－n）（v≥3）                      （1）
（1）式就是多阶曲面上图中顶点与边的关系。当图是完全图时，有e＝v（v－1）/2的关系，把e＝v（v－1）/2代入（1）式得
v（v－1）/2＝3v－6（1－n）
v2－7v＋12（1－n）≤0                          （2）
解这个一元二次不等式（2），得其正根是
v≤（7＋√（1＋48n））/2  （v≥3）
由于顶点数v必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞ （v≥3）       （3）
（3）式中暂用＜ ＞表示其中的数字向下取整。（3）式中的v就是可嵌入亏格是n的曲面上的完全图的顶点数。
    2、平面图中可嵌入的最大完全图的顶点数
平面图的亏格是0，把n＝0代入（3）式中，得
v≤4                                        （4）
（4）式就是可嵌入亏格为0的平面上的完全图的顶点数。
实际中，K1，K2，K3，K4的顶点数都不大于4，都可以嵌入平面上，而K5的顶点数是大于4的，K5就是一个非平面图，不可嵌入平面上。
公式（4）也可以直接从平面图的边与顶点的关系式e≤3v－6 （v≥3）得来。把完全图中边与顶点的关系e＝v（v－1）/2代入上式得
v2－7v＋12≤0  （v≥3）                                  （5）
解（5）式这个一元二次不等式得
v1≤4和v2≤3                                                   （6）
由于v2≤3包含于 v1≤4中，所以实际只有一个根
        v1≤4                                        （6＇）
与上面的（4）式完全同。
3、四色猜测的证明
完全图着色，所需颜色数就是其顶点数，把（3）式中的顶点数v换成颜色数γ，则（3）式变成
γ≤＜（7＋√（1＋48n））/2＞ （v≥3）       （7）
把n＝0代入（7）式中，得
    γ≤4                                        （8）
（8）式就是平面上完全图的色数，是不大于4的。
已知平面图的色数就是其最小完全同态的顶点数，而平面图的最小完全同态的顶点数也是不大于4的（见《平面图最小完全同态的顶点数是不大于4的》，网址是：），所以（8）式也就是任意平面图的色数公式。因为γ≤4，这也就证明了平面图四色猜测是正确的。
极大图是平面图中的一种，当然（8）式也一定适合于极大图，而极大图的顶点着色就相当于其对偶图面的着色，其对偶图正好就是3—正则的平面图，即是地图，因此也就证明了地图四色猜测是正确的。
四色猜测得到证明是正确的。

雷  明
二○一六年十月三十日于长安

注：此文已于二○一六年十月三十日在《中国博士网》上发表过，网址是：


平面（球面）上是不存在五色地图的
——四色猜测证明方法之四
雷  明
（二○一六年十月三十一日）

1、多阶曲面上两均相邻的区域的个数及其着色数
设在某亏格为n的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色地图。这个“国数最小的”地图中也就应有γ个“国家”（这个“国数最小的”地图中的“国家”数γ，实际上就相当于图的最小完全同态的顶点数）。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与别的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域的总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这条边界线中每条边界线都是计算了两次的，所以就有2e＝f（f－1）；又因为地图是一个3—正则图，即每一个顶点都连着3条边（即所谓的“三界点”），所以该地图的总边数也可以写成e＝3v/2，即2e＝3v，从而有3v＝2e＝f（f－1）的关系。用区域数（即面数）f来表示顶点数v和边数e，则有v＝f（f－1）/3和e＝f（f－1）/2。把v＝f（f－1）/3和e＝f（f－1）/2代入到多阶曲面上图的欧拉公式v＋f－e＝2－2n则得到
f2－7f＋12（1－n）＝0                        （1）
解这个关于“国数最小的”地图的区域数f的一元二次方程（1）得正根是
        f＝（7＋√（1＋48n））/2
因为区域数必须是整数，所以上式还得向下取整，得
        f＝＜（7＋√（1＋48n））/2＞                 （2）
式中用＜ ＞表示其中的数字向下取整。又因为f是两两均相邻的“国数最小的”地图的“国数”，即区域数，所以这个“国数最小的”地
图染色时也必须用与其区域数相同的颜色数，所以又有
        γ＝f＝＜（7＋√（1＋48n））/2＞             （3）
从以上的讨论看，这个区域数f只是某一亏格为n的曲面上“国数最小的”地图中的“国数”最大者。若从这个“国数最小的”地图中去掉一条边，或者去掉一个“三界点”顶点及其所连的3条边，该地图中的区域数就都会减少。这个“国数最小的”地图原来是一个区域染一种颜色，那么现在区域数少了，所用的颜色数也就会减少下来。所以上式还可以再增添上“不等式部分”，即
        γ＝f≤＜（7＋√（1＋48n））/2＞             （4）
    2、平面（球面）地图中两两均相邻的区域的个数及其着色数
（4）式中当曲面的亏格为n＝0时，其两两区域均相邻的区域数和色数都是不大于4的，即γ＝f≤4，说明了平面地图中是不存在五个区域两两均相邻情况的。即平面地图中是不存在五色地图的。（4）式就是平面地图中两两均相邻的区划数，也是就是（平面）地图着色的色数，也即地图四色猜测。这就证明了地图四色猜测是正确的。
地图中两两均相邻的区域的个数不大于4（即不存在五色地图）还可以直接用平面图的欧拉公式来证明。把把v＝f（f－1）/3和e＝f（f－1）/2代入到平面图的欧拉公式v＋f－e＝2中，则得到
f2－7f＋12＝0                                （5）
解（5）的一元二次方和得两个正根分别是
         f＝4和f＝3
均小于5，也说明了平面地图中只能存在3个或4个区域两两相邻，而不存在5个区域两两相邻的情况，即不存在五色地图。
3、平面图四色猜测也是正确的
按坎泊的思想，只要能证明平面地图中不存在五色地图，那么地图四色猜测就是成立的。现在已经证明了平面地图中的却不存在五色地图，所以地图四色猜想就是正确的。
地图的对偶图是一个极大图，地图的区域着色，就相当于给其对偶图的顶点着色，所以说地图四色猜测是正确的，极大图的四色猜测也就是正确的了。而由极大图经过去点或去边后得到的任意平面图对于极大图来说，色数只会减少而不会增加，所以任意图的色数也是不会大于4 的，平面图的四色猜测也是正确的。

雷  明
二○一六年十月三十一日于长安

注：此文已于二○一六年十月三十一日在《中国博士网》上发表过，网址是：


反证法证明平面上不存在五色地图
——四色猜测证明方法之五
雷  明
（二○一六年十月三十一日）

五色地图就是需要用五种颜色着色的地图，最小五色地图就是地图中只有五个区域，且每两个区域都是相邻的地图。
按坎泊的想法，如果不存在五色地图时，则地图四色猜测就是正确的。
现在我们假设这种五色地图存在，则一定也存在最小的五色地图。
由于最小五色地图中每一个区域都与其他的四个区域相邻，所以每个区域就有四条边界线，五个区域共有二十条边界线，但每条边界都是两个区域所共有，所以该最小五色地图实际只有十条边界线（即图的边数e＝10）。又由于地图是一个3—正则图，所以有3v（顶点数）＝2e（边数）。把最小五色地图的边数e＝10代入3v＝2e中，得到顶点数v＝20/3，不是整数，这是不符合实际的。否定假设，说明了我们假设的最小五色地图是不存在的。
按坎泊的想法，这也就证明了地图四色猜测是正确的。同样的平面图的四色猜测也是正确的。
雷  明
二○一六年十月三十一日于长安
注：此文已于二○一六年十月三十一日在《中国博士网》上发表过，网址是：

（未完，接下一贴）

雷明85639720

谢谢了。

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，