四色猜测证明的备忘录

雷明85639720

四色猜测证明的备忘录
雷  明
（二○一六年八月十二日）

1、1852年英国的法朗西斯在给地图着色时提出了四色猜测。
2、1879年英国的坎泊宣布他用了颜色交换的技术证明了四色猜测是正确的。但坎泊的证明有漏洞，他没有证明5—轮构形中有两条连通链、且两链有两个以上相交顶点（一个是两链的起始顶点，另外的是两链的交叉顶点）的情况下的构形是否可约。
3、1880年泰特又根据另一个现在看来是并不正确的猜想“每个平面三次图都有哈密顿圈”给出了四色猜想的另一个“证明”。

4、1890年英国的赫渥特构造了一个两条连通链有两个相交顶点的图，正好就是坎泊所遗漏的情况的一种（如图1），但赫渥特与坎泊都不能给该图4—着色。
5、1946年，塔特构造了一个没有哈密顿圈的平面三次图，证明了泰特1880年的“证明”是错误的。
5、1976年美图的阿贝尔等人用电子计算机对近2000个图进行了4—着色。但这不能算做对四色猜测的证明，因为两千个图对于无穷多的图来说仍是个别的、有限的。
6、1990年中国的雷明与懂德周分别根据赫渥特图的特点——有一条环形的g—y链，把b—r链分成了不连通的两部分——从两连通链的任一个相交顶点（已着b色）交换任一部分b—r链，使赫渥特图变成坎泊已证明过的是可约的构形，成功解决了赫渥特图的4—着色问题。雷明先生把这一方法叫“断链法”，因为这一交换，图中所有的连通链都变成了不连通的了。由赫渥特图简化得来的“九点形”图如图2。由于赫渥特图只是一个个别的图，它4—着色并不能说明四色猜测就是正确的，所以在1992年雷明先生就已经提出了，用纯图论的理论，不画图不着色的方法证明四色猜测的设想。

7、1992年英国的米勒等用一种叫做“赫渥特颠倒”的方法给赫渥特图也进行了4—着色。他们同时又构造了米勒图（如图3），但用他们的颠倒法又不能给米勒图进行4—着色，认为颠倒四次后就会出现循环现象。
8、1992年中国的张彧典先生等用一种从现在的观点看，是与米勒是同样的方法——颠倒法，对5—轮构形进行了研究，认为颠倒八次就出现大循环。

9、1992年中国的敢峰先生用一种演绎的方法，在图可以进行4—着色时，不是去完成4—着色，反而设置种种障碍，使一个可4—着色的图变成具有坎泊漏掉了的那种有两条连通链、且两链有两个相交顶点的难着色图（敢峰先生叫它“四色不可解”图），从最基本的赫渥特构形开始，经过了二十步大演绎（也即二十次颠倒），最后也得到一个与米勒图一样的图（如图4）（图画得虽不同，但是因为图是拓扑的，所以同一个图有多种不同的表达方法）。但敢峰先生不象米勒那样，认为该图不能四着色，而是根据图中有一条环形的A—B链，把C—D链分成了不连通的两部分，交换其中任一部分C—D链，都可以使图变成坎泊已证明是可约的构形。应该说敢峰先生计高一筹，是敢峰先生第一个证明了四色猜测是正确的。敢峰先生还发现，当把图4的图施行了一次颠倒（或敢峰先生所说的演绎）后（如图5），图就由BAB型变成了DCD型，图中仍有环形的A—B链，交换A—B环形链内外的任一条C—D链也是可以使图变成坎泊构形（这种交换实质上也是从两连通链D—A和D—B的相交顶点进行的“断链”）。也看到了若再继续施行颠倒，图的“双×夹×型”虽在变化，但图中总是存着A—B环形链的。但他没有发现对图4施行了一次颠倒后，图就变成了一个如图1和图2的赫渥特图，其中产生了经过非“双×夹×型”的两个顶点颜色的环行链A—B（如图5），而图4中的环形链A—B却是经过了“双×夹×型”的三个顶点的。这一事实也说明了米勒图与赫渥特构形是可以相互转化的，若再继续施行一次颠倒，图又变回了米勒构形。但敢峰先生却没有发现米勒图与赫渥特图可以相互转化这一规律。
10、1992年，雷明与张彧典分别又对以下的类似赫渥特图的简化图九点形图进行了研究（如图6，图7，图8，图9）。这几个图形在敢峰先生的研究中是没有看到的。因为敢峰先生是把各种情况下的可4—着色放弃了的，而只研究不可4—着色的情况。
雷明先生把图7，图8，图9归为非赫渥特图类构形，因为他们都可以同时移去两个同色B，而不同于图6（与图2相同）的不能同时移去两个同色B的情况。解决如图6的赫渥特图类构形都用对经过非“双×夹×型”的两个顶点颜色的环行链内外的任一条“双×夹×型”的两种颜色构成的链的交换，使图变成坎泊构形。解决如图7的构形，可以随意先后次序的交换关于两个同色B的链，同时移去两个同色B；也可以交换经过“双×夹×型”的三个顶点的两种颜色的环行链内外的任一条非“双×夹×型”的两个顶点的两种颜色构成的链的交换，使图变成坎泊构形（正因为这一原因，雷先生才把图7的构形与米勒图归为同一类构形）。解决图8和图9的构形，则只能交换两条关于两个同色B的链，同时移去两个同色B：但图8要先从顶点1交换B—D链，后从顶点3交换B—C链；而图9则要先从顶点3交换B—C链，后从顶点1交换B—D链。

当顶点数大于9的形如图8与图9的图，也不能同时移去两个同色B时，就只能用颠倒法先移去一个B，使构形变型，再进行解决。如图10的两个图就是这样解决的。其变形结果有两种可能，一种是变成可同时移去两个同色的形如图8或图9的构形，另一种是变成形如图6的赫渥特构形，再用解决赫渥特图型的办法去解决就可以了。雷先生认为张先生的第八构形就是属于形如图10的这种构形。从这时就可以看出图6与图8（或图9）是可以相互转化的。
张彧典先生则把图8，图6，图9分别归为他的九大构形（见下一个问题）中的第一，第二，第三个构形，而把图7未列入其九大构形之列。张先生采取了雷先生的意见，把第一，第三至第七的六个构形都归入一个类型，但他不知为什么又把第八构形却归入了第二构形。雷先生认为第八构形就是单独的一类，只有这种构形没有自已的单独解法，只能用颠颠法进行转型了（如图10）。

11、2010年张彧典先生得到了米勒图，可能也是看到了敢峰先生的演绎法的原因，也用与敢峰先生相同的方法也对米勒图进行了4—着色，张先生把它叫做“Z—换色程序”。同时，张先生提出了八大构形，依次用1至8次颠倒就可对其进行4—着色，再加上米勒图，张先生认为类赫渥特图类构形只有这九大类型。但张先生与敢峰先生一样，同样也没有看到米勒图与赫渥特构形可以相互转化这一现象。
12、2010年雷明从张彧典先生处获知了米勒图后，也对其进行了研究，发现在米勒图与赫渥特构形是可以相互转化的这一现象，并与张先生等爱好者进行了广泛的网上交流。所以雷先生认为米勒图与图7的构形具有相同的特征：都有经过“双×夹×型”的三个顶点的A—B环形链，解决问题是用交换被环形的A—B链隔开的任一条C—D链，使图变型为坎泊构形的；而对于对米勒图施行了一次颠倒后的图（如图5），雷先生则认为其与图6的构形具有相同的特征：都有经过非“双×夹×型”的两个顶点颜色的环形链（图5中也是A—B链），解决问题是用交换被环形链隔开的任一条“双×夹×型”的两种颜色构成的链（图5中也是C—D链），使图变型为坎泊构形的。不能笼统的只看到都要有A—B环形链，而要看到是图的构形的类型发生了变化。
另外，张彧典先生在最近又构造了几个图（构形），如图11，图12，图13。图11中有一条环形的C—D链，是一个赫渥特图类的构形；图12和图13中都有环形的A—B链，是一个与图7和米勒图相同的构形。而张先生硬要把图13归入他的第三类构形，不知二者之间有什么相同的特征。

14、另外，雷明先生还要根据他早在1992年提出的用纯图论的理论，不画图不着色证明四色猜测的思路，研究了一些不画图不着色的证明四色猜测的方法，这里也就不再一一列出了。可见雷明先生的博文《话说四色问题——研究四色问题三十年之总结》一文（网址是：）和雷先生的其他博文（雷明先生的博客的网址是：）


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

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

雷明85639720

，，，，

雷明85639720

........

雷明85639720

，，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

zengyong

雷明朋友:
     谢谢你给我们提供那么多的有关四色猜想证明的历史资料.

我偶尔看了图1 赫渥特图一下, 发现左边用面与面邻接的方法是否有错误?

右图顶点7g和顶点y5是邻接的; 但左图对应的面没有邻接.

这也说明了用面与面邻接的图表示方法是原始的,不容易看清面与面的邻接关系.

雷明85639720

增勇朋友：
谢谢你指出了我多年来的一个错误的地方，图1的左图是画错了一点，8b不应与其上的那个r相邻，应把7g拉过来与5y相邻。这个图在范益政翻译的沙特朗的《图论导引》书中有，你可以对照一下。右边的极大图在聂祖安翻译的〈图论的例和反例〉一书中有，你都可以看一看。
你的结论很正确，“这也说明了用面与面邻接的图表示方法是原始的,不容易看清面与面的邻接关系.”的却是这样的。现在有此人总是离不开地图，不知道是为什么。

雷明85639720

，，，，