[原创]用三种方法对四色猜测进行证明

雷明85639720

[watermark]

用三种方法
对四色猜测进行证明
雷  明
（二○一○年七月二十四日）
（想看图，请打开DOC格式文件查看）
我总是认为：任何问题的解决，总不是只有一种办法，而是一定有多种办法的，四色问题也是这样。
一、着色法证明四色猜测
这一方法基本上是坎泊早已使用的方法。
1、用坎泊的颜色交换法证明5—轮构形的可约性
坎泊早已证明了任何地图中至少存在着一个国家的邻国数小于等于5，这相当于平面图中至少存在着一个顶点的度小于等于5。这分别就是地图和平面图的不可避免构形集。有了这个有限无素的不可避免构形集，我们就可以只证明少量有限个构形的可约性（即可4—着色性），就可以得到猜测是正确还是错误的结论。这是因为任何地图或平面图中一定存在着其不可避免集中的一种或几种，一个或几个。
坎泊当时证明中的漏洞是没有彻底证明5—构形是不是可约的，而阿贝尔的验证中尽管用了大量的所谓构形，但正好就缺少了5—构形。所以，现在我们还要对5—构形是可约是否可约进行证明，才能为进一步证明猜测打下坚实的基础。我们这里的证明仍旧用的是坎泊创造的颜色交换技术。
5—轮构形对角链间的关系只可能有如图1的几种。图1，a中没有连通的对角链，从任何一个只用了一次颜色的顶点开始进行与其对角顶点所着颜色的色链的交换，即可空出一种颜色给未着色顶点v着上；图1，b中只有一条连通的对角链r—g（或r—y，用虚线表示），可从顶点2或5（或顶点2或4）开始进行b—y链或（b—g）链的交换，即可空出b或y（或b或g）给v着上（因为在连通的对角链上进行交换是空不出颜色的，所以不能交换r—g链和r—y链）；图1，c中

只有一条连通的对角链b—y（或b—g，也用虚线表示），可从顶点2或4（或顶点2或5）开始进行b—g（或b—y）链的交换，即可空出颜色b或g（或b或y）给v着上；图1，d中有两条连通且相交叉的对角链r—g和r—y，交叉点着b色，可从顶点2或5（或顶点2或4）
开始进行b—y或（b—g）链的交换，即可空出b或y（或b或g）给v着上；图1，e中有两条连通且相交叉的对角链b—g和b—y，交叉点是顶点2，着b色，可以分别从两个着r色的顶点1和3开始进行r—g链和r—y链的交换，空出r给v着上；图1，f中也有两条连通且相交叉的对角链b—g和b—y，但两链的交叉点有两个，除了顶点2外，还有另外一个交叉点，也着b色，这个图如果分别从两个着r色的顶点1和3开始进行r—g链和r—y链的交换时，使原来的b—g链和b—y链中的一些顶点由g和y均变成了r，这些顶点有可能在图中本来就是相邻的，而相邻的顶点着同一颜色r显然是不允许的。这样，是乎就不可能同时移去两个r，空不出r给v着上（这一点在一般的文献中均提到了，而在张忠辅教授的《数学的陷阱——四色猜想的各种“证明”》一文中又特别提出了这一点），这样一来，5—轮构形的中心顶点v似乎没有办法着上已用过的四种颜色之一。真的就没有办法了吗？不是的，而是有办法解决的。

我们可以想办法使图1，f变成图1，a的形式，让图中不存在任何连通的对角链，然后再按图1，a的交换办法给v着上已用过的四种颜色之一。图1，f中的两条连通的对角链是相交叉的，两链共同的顶点除了顶点2外，还有另外一个，都着色是b，只要想办法改变这两个顶点之一的颜色，就可使图1，f变成图1，a的形式，使图中不存在任何连通的对角链。要改变这两个顶点的颜色，就必须从该顶点开始交换两条交叉链共有的颜色与共同没有的颜构成的色链b—r，这样，图1，f就分别变成了图2，a和图2，b两图了，该两图都是图1，a的模式，图中不存在任何连通的对角链。这时再任进行一次坎泊的颜色交换，就可空出一种颜色给v着上。
另外，从以上的颜色交换过程中我们还注意到，顶点2是一个非常关键的顶点，它在5—轮构形中的两个相邻的轮沿顶点1和3着有同一颜色r，且只有r色用了两次，别的颜色都只用了一次。在图1的各种情况下，只要从顶点2开始进行b—r链的交换，都可使图1的各种情况变成图1，a的情况，即图中不存在有任何连通的对角链。这就是说，只要是5—轮构形，可以不管它是什么情况，先从顶点2开始对其所着颜色与其相邻的两个顶点所着颜色构成的色链进行交换后，再进行一次坎泊的颜色交换，该5—轮构形就可以4—着色，也就是说这个5—轮构形是“可约的”。
过去坎泊已证明了0—轮、1—轮、2—轮、3—轮、4—轮构形的可约性，至此，地图或平面图不可避免集中的各种构形就都成了可约的了，这样我们就可以对四色猜测进行证明了。
2、任何地图或平面图着色时四种颜色的确够用了
给一个顶点数为n（n为自然数）的平面图（或地图的对偶图），图中一定存在着度d≤5的顶点。把这些顶点从图中去掉，图仍是一个平面图，图中又会产生新的度d≤5的顶点，一直这样的取下去，最后图将成为一个顶点数n≤4的图，这种情况下，最复杂时只可能是一个K4图，着四色是绝对没有问题的。
现在再沿相反方向向回走，给上面的n≤4的图中增加一个原来去掉的度d≤5的顶点，图中就有n≤5个顶点，这时最复杂时也只能是4—轮，坎泊早已证明了4—轮是可以4着色的；若再增加一个顶点时，图中就有n≤6个顶点，这时最复杂的可能就是5—轮，从上面的证明可以看出，5—轮4着色也是没有问题的，即增加的这个顶点着上已用过的四种颜色之一是可以办到的。继续增加顶点，因为所增加的顶点都是原来从图中所去掉的顶点，其度d都是≤5的，这个顶点一定是可以着上四种颜色之一的，直到把从图中所去掉的顶点全部增加进去，每增一个顶点都是可以着上已用过的四种颜色之一的，这样整个图也就只用了四种颜色。这就证明了四色猜测是正确的。
二、图论法证明四色猜测
    这一方法不对任何图着色，只研究图的结构，推导出任意图的色数与图的密度的关系，即任意图色数的界，再把平面图的密度不大于4的特点代入这个界中，就得到任何平面图着色的色数总不大于4的结论。证明了四色猜测是正确的。
1、图的色数、顶独立集、完全同态的关系
在任何图中：互不相邻的顶点都可以着以相同的颜色；互不相邻的顶点也可以划归在同一个顶独立集内；互不相邻的顶点也可以同化为一个顶点。这样，任何图的色数γ就等于图的最少的顶独立集的个数β，也等于图的最小完全同态的顶点数α，应有γ＝β＝α的关系。现在的关键问题是要求出图的最小完全同态的顶点数α与图的最基本参数——密度ω的关系。
2、最大团外的团向最大团的同化
任何图中最大团Kω的顶点数ω就是图的密度。最大团外的任何团Km（m≤ω）的各个顶点与最大团中所相邻的顶点数只能是小于等于ω－1个，否则，图的密度就要比ω大了。这些属于最大团中的顶点的交集一定是一个顶点数小于等于ω－m个、且属于最大团中的Kn（n≤ω－m）团，那么，最大团Kω中至少还应有ω－m个顶点可以让团Km中的各个顶点同化到最大团中来。
3、单条道路向最大团的同化

一条道路Pn是由若干个K2团相互邻接而成的，应该说，道路中的每个顶点都是可以同化到顶点数大于等于2的最大团中去的，但是当道路中各顶点都与最大团中相同的ω－2个顶点相邻，且道路的两个端点顶点同时又还与最大团中另外的两个顶点（属于最大团中的一个K2团）之一相邻时的情况下，道路中各顶点只就只可能向这个属于最大团中的K2团中的两个顶点之一进行同化，这样问题就简化成了一条道路向一个K2团同化的问题了（如图2，图中只画出了部分关键顶点和边）。又可以首先把道路本身同化成一个K2团（道路本身的最小完全同态就是K2团），这时，问题就又变成为一个K2团向另一个K2团同化的问题了（如图3）。
图2中的两图由于道路的奇偶性的不同，道路自身同化后分别就成为图3的四个图了。图2，a中当n为奇数时，就成为图3，a了，总有一个顶点同化不到最大团中去；图2，b中当n为偶数时，就成为图3，d了，也总有一个顶点同化不到最大团中去。这时，图同化的最后结果——最小完全同态Kα的顶点数α就要比图的密度ω大1了（如果是把Pn中各顶点直接向最大团中的那个K2团进行同化时，也会得到同样的结果）。如果道路Pn是一个回路（即圈），也可得到同样的结果。

而图2，a中当n为偶数时，就成为图3，b图了；图2，b图中当n为寄数时，就成为图3的c了；该两图的所有顶点都可同化到最大团中去。这时候，图同化的最后结果——最小完全同态Kα的顶点数α就与图的密度ω是相同的了。
这里，我们把总有一个顶点同化不到最大团中去的道路称为不可同化道路。
4、多条道路向最大团的同化
如果有以上的不可同化道路S条，但各条道路之间并没有形成联，各条道路同化不到最大团中去的那S个顶点因其本身就不相邻还可再同化为一个顶点（因为S条道路间没有联，所以同化时总可以把各条道路互不相邻的顶点作为不可同化的顶点，然后再将其同化为一个顶点），其实质仍与只有一条不可同化道路的情况一样，最终也只有一个顶点同化不到最大团中去。
如果S条道路间均有联存在，则各条道路同化不到最大团中去的那S个顶点因其本身就是相邻的而不可能再同化成一个顶点，所以就有S 个顶点同化不到最大团中去。这样，图的最小完全同态的顶点数α就应是α＝ω＋S，其色数也就是γ＝ω＋S。现在的问题是要确定S与图的密度的关系。
5、任意图着色色数的界
在S条不可同化道路的联中，可能的最大团只能是2S（每一条道路提供两个顶点即一个K2团，S条道路的联就含有由S个K2团构成的K2S团，其顶点数是2S），且2S一定是小于等于图的密度的，即有2S≤ω或S≤ω/ 2。由于道路的条数必须是整数，所以S还得向下取整，即S≤ 。这时就有图的色数的上界是：γ＝ω＋S≤ ＋ ≤ ，由于图的色数至少是大于等于图的密度的，即γ≥ω，把上两式合写在一起就得到任意图着色色数的界：ω≤γ≤ 。
6、四色猜测的证明
已知平面图的密度是不大于4的，这就有可能使我们把仅有的四种密度值代入到任意图着色色数的界中，结果得到任何平面图的色数都是小于等于4的。初看起来在ω＝4时，其色数有可能大于4，但在这种情况下的图已不再是平面图了（如图4，a的色数是5，图4，b的色数仍是4，但两图都不是平面图，因为图中出现了交叉边。）。由此可以得出任何平面图着色时，其色数一定不会大于4，即γ平≤4。这就证明了平面图的四色猜测是正确的。

地图本身就是平面图，而平面图的对偶图仍是平面图。给地图面上的着色实质上就是给其对偶图的顶点的着色。任何平面图顶点着色时，四种颜色够用了，那么任何地图着色时，四种颜色也一定够用。这也就证明了地图四色猜测也是正确的。
7、具体图色数的确定
当ω＝1时，色数一定是1，即有γ＝1＝ω；
当ω＝2时，若图中有奇圈，则色数是3，即有γ＝3＝ω＋1，因为这种情况下的奇圈中，对于任一个K2团，都有一条不可同化道路，所以有γ＝ω＋S＝2＋1＝3；若图中没有奇圈，色数则是2，即有γ＝2＝ω；
当ω＝3时，若图中有奇轮，则色数是4，即有γ＝4＝ω＋1，因为这种情况下的奇轮中，对于任一个K3团，都有一条不可同化道路，所以有γ＝ω＋S＝3＋1＝4；若图中没有奇轮，色数则是3，即有γ＝3＝ω；
当ω＝4时，其色数总是4，即有γ≡4，因为ω＝4的图，当色数大于4时，图就不再是平面图了（见图4）。
8、图值函数色数的界
线图的密度等于图的最大度，所以线色数的界是：Δ≤γ线≤ ；全图的密度等于图的最大度加1，所以全色数的界是：Δ＋1≤γ全≤ ；平面图的面色数等于其对偶图的顶点着色色数，所以，平面图面色数的界也是：γ平面≤4；平面图的整图的密度是max（d线度＋d面度）＋1，所以其色数的界是：max（d线度＋d面度）＋1≤γ整≤ ；从以上可以看出，图值函数的密度只与图的线度或面度有关，即ω函数＝f（d线度，d平面图的面度），所以图值函数色数的界是：f（d线度，d平面图的面度）≤γ图值函数≤ 。
9、四色猜测是正确的
从以上证明可以看出，平面图的四色猜测和地图的四色猜测都是正确的。密度是4的平面图的色数一定是4；密度是3时，若图中有奇轮，其色数是4，否则是3；密度是2时，若图中有奇圈，其色数是3，否则是2；密度是1时，色数也一定是1。任何地图都是平面图，任何地图着色时，其色数都不会大于4。
三、数学推导法证明四色猜测
本方法是纯粹用数学推导的办法，从曲面上的欧拉公式推导出了任意平面图着色的色数一定是小于等于4的。
1、曲面上图的欧拉公式
已经得到证明是绝对正确的可嵌入到任何亏格曲面上的图的欧拉公式如下：
    v＋f＝e＋2－2n                               （1）
式中v、f、e、n分别是图的顶点数、面数、边数和曲面的亏格（也就是图的亏格）。这里曲面的亏格应是图所可嵌入的曲面的最小亏格。其证明方法可见人民邮电出版社2007年9月出版，美国Gary•Chartrand  Ping•Zhang编著，范益政、汪毅、龚世才、朱明翻译的《图论引导》一书。这个公式也适用于亏格n为0的平面图，当n＝0时公式变成
    v＋f＝e＋2                                   （2）
2、任意图的亏格
任何图的亏格就是其所能嵌入的曲面的最小亏格。
通过曲面上的图的欧拉公式可以推导出任何图所能嵌入的曲面的最小亏格。其推导过程如下：
能嵌入到与图的亏格n相同的曲面上的图，其顶点v、边e和面f间的关系是一定能适合该曲面上的图的欧拉公式（1）（v＋f－e＝2－2n）的。
设f个面分别为f1，f2，……，ff，用ei（1≤i≤f）表示面fi边界上的边数，所以有ei≥3，又因为每一条边均是属于两个面所共有，所以有
3f≤ ≤2e                                 （2）
（2）式中，2e是图中所有边的2倍，包括悬挂边和桥边在内，而 却只是所在面（即圈）的边界条线的总和，所以有 ≤2e，又由于任何面的边界数都大于等于3，所以在面数相同情况下，就有3f≤ ，即有3f≤ ≤2e的关系。所以又有
3f≤2e  和  f≤2e / 3                          （3）
上面的3f≤2e和f≤2e / 3也可以这样来理解：如果图的所有面均是3—边形面，则有3f＝2e和f＝2e / 3，这是相同顶点时的图中边和面最多的情况；如果图中的顶点数不变，而含有边数大于3的多边形的面时，则有3f＜2e和f＜2e / 3。二者写在一起，这时就有3f≤2e和f≤2e / 3。把（3）式中的f≤2e / 3代入到曲面上的图的欧拉公式（1）v＋f－e＝2－2n中，得
        v＋ －e≥2－2n
两边同除以2得
         ＋ － ≥1－n
         ≥1－n
         － ≥1－n
两边同乘以－1，改变不等式符号的方向
         － ≤－1＋n
解关于n的不等式，并移项整理得
        n≥ － ＋1
图或曲面的亏格都必须是整数，所以上式还得向上取整，得
        n≥ （v≥3）                         （4）
该公式也就是任意图的亏格与顶点v和边e有关系。
公式（4）还可以变形成
    n≥ （v≥3）                       （4＇）
（4）和（4＇）式中的 表示其内的值向上取整，等式对应完全图，不等式对应非完全图。
3、完全图的亏格
1968年由Gerhard•Ringel和J•W•T（Ted）Youngs给出的当n≥3时，完全图Kv的亏格的公式是：
完全图Kv的亏格＝ （v≥3）        （5）
该公式可以通过上面的公式（3）或（4＇）式任意图的亏格和完全图的边数与其顶点数的关系式推导出来。推导过程如下：
已经知道顶点数是v的图的边数e与顶点数v的关系是
e≤                                     （6）
把（6）式代入（4＇）式n≥ （v≥3）中得
        n≥
         ≥
         ≥
≥ （v≥3）                      （7）
公式（7）也是任意图的亏格。（7）式与（4＇）式不同的地方是：（7）式中n只与v有关，而（4＇）式中n却与v和e都有关，且（7）式是由（4＇）式推导而来，两式实质上是一回事。同样（7）式中的等式对应的是完全图，不等式对应的是非完全图。当（7）式取等式时就是上面的公式（5）。所以公式（5）和（7）都包含了顶点数是v的完全图Kv的亏格。
4、赫渥特的地图着色公式
1890年赫渥特早就得到了多阶（任何亏格）曲面上的着色公式，这个公式断言，能嵌入亏格为n的曲面上的所有图的色数是：
γn≤ （n≥1）                    （8）
（8）式中n为曲面的亏格数（也是图的亏格），γn是能嵌入亏格为n的曲面上的所有图的色数。 表示其内数字向下取整。由于当时赫渥特对自已所构造的图——Haewood—图（平面图，其亏格是n＝0）不能进行4—着色，所以就对他的公式附加了成立的条件n≥1。
赫渥特的地图着色公式（8）是可以通过以上的公式（5）和（7）完全图的亏格推导出来的。推导方法如下：
对任完全图KV的亏格n＝ （v≥3）（公式（5）和（7））在未向上取整之前的形式n＝ 进行变形，得到
    12n＝（v－3）（v－4）
       ＝v2－7v＋12
即
        0＝v2－7v＋12－12n
         ＝v2－7v＋12×（1－n）
解这个关于v的一元二次方程
        Δ＝（－7）2－4×1×12×（1－n）
　　　　　＝49－48＋48n
          ＝1＋48n
其两个根是
        v1＝ ＝
        v2＝ ＝
由于在v2＝ 中，当n≥1时，v2＝ ≤0，不符合题意，因为任何图的顶点数都是不会小于1的，所以舍去不要。该一元二次方程只有一个根v1＝ 。
因为完全图的色数就等于其顶点数，所以又有可以嵌入亏格为n的曲面上的完全图Kv的色数为
        γn＝
又因为完全图的色数是与其有相同顶点数的图中的最大者，所以又有可以嵌入亏格为n的曲面上的任意图的色数为
        γn≤
由于色数必须是整数，所以上式还得向下取整，即有
γn≤                               （9）
公式（9）就是赫渥特的地图着色公式（8），式中的γn是亏格为n的曲面（图的亏格也是n）上的图的色数。
5、四色猜测的证明
公式（8）或（9）即是任意亏格下的曲面上的地图着色公式，那么其对于亏格为0的平面图也应该是适合的。的确当n＝0时，公式（8）的结果是γn≤4，这就是四色猜测的数学表达式。这就是说，任何平面图着色时，其色数一定是小于等于4的。这时我们就可以把（8）或（9）式改写成
    γn≤ （n≥0）                   （10）
赫渥特的这个公式是正确的，其中也已包括了平面图（n＝0）在内，这也就使猜测得到了证明是正确的。
    以上对四色猜测的证明就说明了任何问题的解决决不可能就只有一种办法的。
                        雷  明
              二○一○年七月二十四日于长安