数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 3913|回复: 3

泰特猜想是正确的,四色猜测正确! ——四色猜测的纯理论证明

[复制链接]
发表于 2017-4-19 09:32 | 显示全部楼层 |阅读模式

泰特猜想是正确的,四色猜测正确!
——四色猜测的纯理论证明
雷  明
(二○一七年四月十八日)

1880年泰特提出了“无割边的3—正则平面图的可3—边着色与其可4—面着色等价”的猜想。因为地图本身就是一个无割边的3—正则的平面图,所以说,如果这个猜想是正确的,则只需证明无割边的3—正则平面图都是可3—边着色的,就可以证明地图的四色猜测是正确的。又因为给地图的面的着色就是对其对偶图——极大平面图——的顶点着色,又可得到极大平面图的色数是不大于4的结论。还因为极大平面图经“去点”和“减边”运算后的图的色数只会比极大图减少而不会再增大,所以也就有任意平面图的色数都不大于4的结论。平面图的四色猜测也就得到了证明是正确的。四色猜测就得到了最终的证明是正确的。
1、泰特猜想是正确的
1、1  可3—边着色的无割边的3—正则平面图是可4—面着色的
已知条件是给定图是可3—边着色的,那么图中就只有三种颜色的边。每两种颜色所夹的面用一种颜色表示,共需用三种颜色,分别用Ⅰ、Ⅱ、Ⅲ表示。图中的任何面最少也有两种颜色的边,所以该面一定可以着上该三种颜色中的某一种。但图中若有奇数边的面时,则这个面中最就必须得有三种颜色的边出现。这时,上以三种颜色中的任一种都不能给该面着上,就得要用第四种颜色Ⅳ了。但也不会多于四种,因为图中只有三种颜色的边,每个面中最多也只可能出现三种颜色的边,所以面着色所用的颜色数是不会多于四种的。如果图中只有四边形的面,每个面中都只有两种颜色的边,那么这个图的面着色用三种颜色就够了。如正六面体就是这样,其每个面都是四边形,每个面都只有两种颜色的边,面着色时的色数就是3,是小于4的。这也就证明了可3—边着色的无割边的3—正则平面图是可4—面着色的。
1、2  可4—面着色的无割边的3—正则平面图是可3—边着色的
已知条件是给定图是可4—面着色的,所用四种颜色分别是A、B、C、D。图中每两种颜色的面都有一条共同的边界,四种颜色的面间就有六种类型的边界,即A—B、A—C、A—D、B—C、B—D和C—D。这六种边界中,A—B与C—D的两对颜色是互斥的,不可能相邻,A—C与B—D也不可能相邻,A—D与B—C也不可能相邻。但两对互斥的边界用同一种颜色完全是可以的,所以图中也只可能出现三种不同颜色的边界,不会多也不会少。这也就证明了可4—面着色的无割边的3—正则平面图也是可3—边着色的。
1、3  泰特猜想,正确!
通过以上正反方向的证明,就可以证明泰特的猜想是正确的。这样就可以只证明无割边的3—正则平面图是可3—边着色的,就可以解决问题了。
2、无割边的3—正则平面图都是可3—边着色的
已知图量个无割边的3—正则平面图。
2、1  由于3—正则图的顶点数一定是偶数,所以无割边的3—正则平面图一定是可以划分成一个或若干个偶圈的,偶圈边着色两种颜色就够了,所以这些圈一定是一条或多条的边2—色圈。图中除此以外的任可边都是两端均连结着边2—色圈上的、且只连接着同样两种颜色的边的顶点,又因这些边之间互不相连,所以是可以同时都着上边2—色圈以外的第三种颜色的。这就证明了无割边的3—正则平面图都是可3—边着色的。
2、2  图的边着色,就是对其线图的顶点着色。所谓线图就是把原图的边作为顶点,按原图中边与边的相邻关系作新的边,所得到的新图,就是原图的线图(也叫边图)。
2、2、1  3—正则平面图中各顶点的度均是3,所以其线图中的最大团的顶点数最大也只能是3(即线图的密度是3),着色时至少也要3种颜色。
2、2、2  3—正则平面图中各面的边数都是大于等于3的多边形面,这些多边形面在其线图中也都是以边数大于等于3的圈(面)出现的。圈在顶点着色时,色数也一定是不大于3的。所以该线图的色数也一定是不会大于3的。
2、2、3  3—正则平面图中各边的两端都连着四条边,表现在其线图中就是各顶点的度均是4。线图的各顶点四周是四个边数大于等于3的面,所以线图中不可有轮出现,更不会有轮沿数大于等于3的奇轮出现没有3—轮以上的奇轮,所以该线图的色数也就不可能大于3。唯有正四面体的线图,是所有顶点都处在一个4—轮的中心顶点的图,而4—轮的色数也是3,正四面体的线图的色数也是3,所以正上面体也是可以3—边着色的。
以上三点也可以证明无割边的3—正则平面图都是可3—边着色的。
2、3  设有n个面的无割边的3—正则平面图是可3—边着色的,现在证明n+1面时,其也是可3—边着色的。
在一个面数为n的无割边的3—正则平面图的某个面内增加一条边,把一个面分成两个面就可以达到目的。在某个面内任两条边中各取一个点a和b,并把a和b用边相连接,a和b就变成了两个新的“三界点”,边a—b就把一个面分成了两个面,图中也就增加了一个面,面为n+1个面。同时图中也增加了两个顶点和三条边,增加的边数也是增加的顶点数的1.5倍,符合3—正则平面图的要求。
现在只要证明这个图还是一个无割边的3—正则图和仍是可3—边着色的就可以了。
2、3、1  证明这个有n+1个面的图仍是一个3—正则的平面图
因为无割边的3—正则的平面图中有e=∑epi/2=(ep1+ep2+……+epn)/2的关系(式中ep是各面的边数),所以3—正则平面图中奇数边面的总个数一定是偶数。
2、3、1、1  若a和b两点所在的边的两个相邻面原来都是偶数边面时,现在则都成了奇数边面,奇数边面增加了两个,但偶数+2仍是偶数,奇数边面的总个数仍是偶数:
2、3、1、2  若a和b两点所在的边的两个相邻面原来都是奇数边面时,现在则都成了偶数边面,奇数边面减少了两个,但偶数一2仍是偶数,奇数边面的总个数仍是偶数:
2、3、1、3  若a和b两点所在的边的两个相邻面原来的边数是一奇一偶时,则现在仍是一奇一偶,奇数边面的总个数没有发生变化,仍是偶数。
可见,a和b两点所在的边的两个相邻面的边数的改变对3—正则平面图中的奇数边面的总个数并无影响。
现在再看一看被分开成两个面的那个面边数的变化对图中奇数边面的影响:
2、3、1、4  若被分开成两个面的那个面原来是奇数条边时,现在的边数则是比原来多了两条的奇数,所分成的面只能是一个奇数边面和一个偶数边面。这等于说图中减少了一个原来的奇数边面,除了增加了一个偶数边面外,又增加了一个奇数边面,相当于图中奇数边面的总个数并未发生变化,仍是偶数;
2、3、1、5  若这个被分开成两个面的面原来是偶数条边时,现在的边数则是比原来多了两条的偶数:
一种情况是分成两个偶数边面,图中奇数边面的总个数仍没有发生变化。
另一种情况是分成两个奇数边面,等于说图中减少了一个原来的偶数边面,但又增加了两个奇数边面,但偶数+2仍是偶数,奇数边面的总个数仍是偶数;
2、3、1、6  从这两个方面来分析,结果都是图中的奇数边面的总个数仍是偶数。n个面的奇数边面总个数是偶数,现在n+1个面的奇数边面仍然是偶数,符合无割边3—正则平面图的要求。该图仍然是一个无割边的3—正则平面图,说明了有n+1个面的图仍是一个无割边的3—正则平面图。
2、3、2  证明这个有n+1个面的图仍是可3—边着色的图
现在再来看看a和b两点所在的边原来所着的颜色对这个有n+1个面无割边的3—正则图的3—边着色有什么影响:
图中因为增加了一个面而增加的两个顶点,虽不能单独构成一个偶圈,但它却是原来图中两条边上的点(如图1和图2)。
2、3、2、1        两条边原来着色不同的情况:

如果a点所在的边原来着1色,那么这条边一定既是1—2边2—色圈上的一条边,又是1—3边2—色圈上的一条边;如果b点所在的边原来着2色,那么这条边也一定既是1—2边2—色链圈上的一条边,又是2—3边2—色圈上的一条边(如图1,a和图1,c);两条边共同都是1—2边2—色圈上的边;这条1—2边2—色圈上增加了两个顶点,同时也增加了两条边,仍是偶数,还是一条偶数的边2—色圈;所增加的这两条是位于原圈上的边,在1—2边2—色圈中,对位于a和b两点同一侧的所有边进行1、2二交换后(如图1,d),一定能给a和b两侧所连的边着上1或2两种颜色(这种对1、2二色的交换与原先着有颜色3的边并无任何关系,并不影响他们的颜色)。给所增加的、把原来的面分成两个面的a—b边着第三种颜色3就可以了(如图1,b和图 1,d)。
2、3、2、2        两条边原来着色相同的情况:

如果a和b两点原来所在的边都着2色(如图2,a和图2,c),那么这两条边共同都是1—2—1和2—3—2两种边2—色圈上的两条边(这里我们只取一种2—3—2边2—色圈),虽增加了两个顶点,但也同时增加了两条边,该边2—色圈仍是一条有偶数边的边2—色圈。与以上图1中的处理办法相同,所增加的两条边,也一定能着上2或3两种颜色,所增加的把原来面分成两个面的a—b边,也可以着上第三种颜色1(如图2,b和图2,d)。
以上两点实际上只是对a和b所在的两条边处在同一条边2—色圈上而言的。但我们知道同一种边2—色圈并不是只有一条,若a和b所在的两条边是处在不同的边2—色圈的情况下时,又将如何处理呢。我们来看下面的图3。
2、3、2、3        两条边原来不在同一个边2—色圈上的情况:

在图3,a中,a和b两点所在的边原来就不在同一条1—2—1边2—色圈上,这时我们可以把其中一个边2—色圈上各边的颜色1和2进行互换,得到如图3,b的图(这样的交换对着色为3的边同样并无影响)。我们发现,由于这一交换,图3,b的图中,虽然a和b两点所在的边仍处在不同的1—2—1边2—色圈上,但却又处在了同一条1—3—1(或2—3—2)的边2—色圈上了。这时,就与以上2、1和2、2中所谈的情况完全相同了,可以用与2、1和2、2中同样的方法进行处理。最后得到可3—边着色的图(如图3,c)。
2、3、2、4  这也就证明了任何一个无割边的3—正则平面图都是可3—边着色的。
2、3、3  以上我们是对有n+1个面的无割边的3—正则平面图进行证明的,同样的也可以对有n-1个面的无割边的3—正则平面图进行证明是可3—边着色的。这只要从有n个面的图中去掉一条边即可办到。
2、4  现在已经证明了无割边的3—正则平面图都是可3—边着色的,这也就等于验证了任何无割边的3—正则平面图也都是可3—边着色的结论是正确的,也就验证了任何无割边的3—正则平面图都是可4—面着色的结论也是正确的。最终也就验证了地图四色猜测是正确的。
3、四色猜测的证明
我们已经证明了泰特的猜想:“无割边的3—正则平面图的可3—边着色等价于其可4—面着色”是正确的。现在又证明了每一个无割边的3—正则平面图都是可3—边着色的。当然也就证明了任何无割边的3—正则平面图(地图)都是可4—面着色的,即证明了地图四色猜测是正确的。地图四色猜测是正确,则其对偶图——极大图平面图的顶点着色的色数也一定是小于等于4的,进而由极大图平面图经减边和去点得到的任意平面图的色数也一定是不会大于4的,平面图的四色猜测也是正确的。到此也就证明了四色猜测是正确的。


雷  明
二○一七年四月十八日于长安

注:此文已于二○一七年四月十九日在《中国博士网》上发表过,网址是:

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-31 01:46 , Processed in 0.110213 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表