[原创]用坎泊的颜色交换法证明5—轮构形的可约性

雷明85639720

[watermark]

用坎泊的颜色交换法
证明5—轮构形的可约性
雷  明
（二○一○年七月十日）
（要看图，请打开DOC格式文件查看）
坎泊早已证明了任何地图中至少存在着一个国家的邻数小于等于5，这相当于平面图中至少存在着一个顶点的度小于等于5。这分别就是地图和平面图的不可避免构形集。有了这个有有限无素的不可避免构形集，我们就可以只证明少量有限个构形的可约性（即可4—着色性），就可以得到猜测是正确还是错误的结论。这是因为任何地图或平面图中一定存在着其不可避免集中的一种或几种，一个或几个。坎泊的证明中的漏洞就是没有证明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给v着上（这一点在一般的文献中均提到了，在张忠辅教授的《数学一陷阱——四色猜想的各种“证明”》一文中又特别提出了这一点），这样一来，5—轮构形的中心顶点v似乎没有办法着上已用过的四种颜色之一。真的就没有办法了吗？不是的，而是有办法解决的。
我们可以想办法使其变成图1，a的形式，让图中不存在任何连通的对角链，然后再按图1，a的交换办法给v着上已用过的四种颜色之一。图1，f中的两条连通的对角链是相交叉的，两链共同的顶点除了顶点2外，还有另外一个，都着色是b，只要想办法改变这两个顶点之一的颜色，就可使图1，f变成图1，a的形式，使图中不存在任何连通的对角链。要改变这两个顶点的颜色，就必须从该顶点开始交换两条交叉链共有的颜色与共同没有的颜构成的色链b—r，这样图1，f就分别变成了图2，和图2，两图了，该两图都是图1，a的模式，图中不存在任何连通的对角链。这时再任进行一次坎泊的颜色交换，就可空出一种颜色给v着上。

另外，从以上的颜色交换过程中我们还注意到，顶点2是一个非常关键的顶点，它在5—轮构形中的两个相邻的轮沿顶点1和3着有同一颜色r，且只有r色用了两次，别的颜色都只用了一次。在图1的各种情况下，只要从顶点2开始进行b—r链的交换，都可使图1的各种情况变成图1，a的情况，即图中不存在有任何连通的对角链。这就是说，只要是5—轮构形，可以不管它是什么情况，先从顶点2开始对其所着颜色与其相邻的两个顶点所着颜色构成的色链进行交换后，再进行一次坎泊的颜色交换，该5—轮构形就可以4—着色，也就是说这个5—轮构形是“可约的”。

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