（5，5）构形和（5，6）构形的可约性

雷明85639720

（5，5）构形和（5，6）构形的可约性
——与张彧典朋友共同讨论
（二○一八年四月二十九日）

1、（5，5）构形和（5，6）构形的产生
四色猜测于1852年提出，1879年坎泊给了一个还有遗漏的证明，1890年赫渥特用自已构造的赫渥特图指出了这个漏洞之所在。这就是5—轮构形中当有两条连通切相交叉的A—C链和A—D链时，待着色顶点V该如何着色的问题。因为这种构形第一次出现在赫渥特图中，所以就把这种构形叫H—构形（H是赫渥特英文保的第一个英文字母）。由于H—构形，在当时认为是既不能空出A，V，D三色之一，也不能同时移去两个同色B（从现在有观点上看，H—构形是可约的，赫渥特图也是可4—着色的。由于H—构形不能证明是可约的，所以在1904年Wernicke提出用（5，5）构形和（5，6）构形代替H—构形（如图1）。

1976年阿贝尔等的证明就是用（5，5）构形和（5，6）构形来代替H—构形的，其虽然证明了（5，5，）和（5，6）是不可免的，但却没有证明其是否可约。如阿贝尔在《四色地图问题的解决》一文中说（5，5）构形和（5，6）构形“这两个（不可约）构形构成一个不可避免集，即是，由于这些计算适用于任何平面三角剖分（任何顶点的度数不小于5），所以每个这样的平面三角剖分都含有这个不可避免集的两个构形之一。”还说“这个去荷手续产生的不可避免集由两个构形组成：一个5度顶点，由一条棱同另一个5度顶点相连，以及一个5度顶点，由一条棱同一个6度顶点相连。这些构形不是可约的。”在有些文献资料（如王树禾的《图论》一书）中也就只说了（5，5）构形和（5，6）构形是不可免构形，也只字不提是事可约的问题。
2、（5，5）构形和（5，6）构形可约性的证明

（5，5）构形和（5，6）构形这两个构形其中一个的待着色顶点是相邻的两个5—次的顶点（即双5—轮），又一个的待着色顶点是一个5—次顶点和一个6—次顶点。又因为着色时，只能是一个顶点一个顶点的着，所以在这两个V中，当有一个着上颜色时，另一个也至少要与着了四种颜色的顶点相邻。所以这两个构形的轮沿顶点就应是如图2所示。这时无论把那一个待着色顶点着上A色时，另一个待着色顶点总是与着了四种颜色的顶点相邻。
    因为是用（5，5，）构形和（5，6）构形来代替H—构形的，所以还至少要保证其围栏顶点以外的链要含有H—构形中的连通的A—C链和A—D链相交叉，不能简单的通过一次空出颜色的颜色交换技术空出A，C，D三种颜色之一来给V着上。
实际上，若把我的H—构形的不可免集中的a类，b类，c类构形中顶点2的A色去掉，这些构形就都变成了只含有（5，5）构形的构形（其顶点3，4，5，1， 7，6的颜色正好就是图2中（5，5）构形围栏顶点的颜色），也可以通过增加顶点的办法使图变成含只有（5，6）构形的构形；而我的H—构形的不可免集中的d类构形若把顶点2的颜色A去掉，则就是只含有（5，6）构形的构形（其顶点3，4，5，1，7，6的颜色正好就是图2中（5，6）构形围栏顶点的颜色），也可以通过减少顶点的办法使图变成只含有（5，5）构形的构形。
2、1  a类（5，5）构形（如图3，a），给其上边一个V着上A（如图3，b），就是我的a类H—构形，是可约的。给其下边一个V着上A（如图3，c和图3，d），图中仍含有环形的A—B链，也是一个a类构形，也是可约的。

2、2  b类（5，5）构形（如图4，a），给其上边一个V着上A（如图4，b），就是我的b类H—构形，是可约的。给其下边一个V着上A（如图4，c和图4，d），图中仍含有环形的C—D链，也是一个b类构形，也是可约的。

2、3  c类（5，5）构形（如图5，a），给其上边一个V着上A（如图5，b），就是我的c类H—构形，是可约的。给其下边一个V着上A（如图5，c和图5，d），图中仍不含有任何环形链，也是一个c类构形，也是可约的。图6是c类（5，5）构形的另一种形式。


2、4  a类（5，6）构形（如图7，a），是在a类（5，5）构形顶点6和7中间增加了一个B色顶点。给其上边一个V着上A（如图7，b），就是一个可以同时移去两个同色B的K—构形（如图7，b）。给其下边一个V着上A（如图7，c和图7，d），可以先从顶点8交换A—B链，使图中连通的A—C链和A—D链断开，图成为K—构形而可约（如图7，e）。

2、5  b类（5，6）构形（如图8，a），是在b类（5，5）构形顶点6和7中间增加了一个B色顶点。给其上边一个V着上A（如图8，b），就是一个可以同时移去两个同色B的K—构形（如图8，b）。给其下边一个V着上A（如图8，c和图8，d），可以先从顶点8交换A—B链，使图中的A—C和A—D连通链断开，图成为K—构形而可约（如图8，e）。

2、6  c类（5，6）构形（如图9，a），是在c类（5，5）构形顶点6和7中间增加了一个B色顶点。给其上边一个V着上A（如图9，b），就是一个可以同时移去两个同色B的K—构形（如图9，b）。给其下边一个V着上A（如图9，c和图9，d），可以先从顶点8交换A—B链，使图中的A—C和A—D连通链断开，图成为K—构形而可约（如图9，e）。

2、7  d类（5，6）构形（如图10，a），给其上边一个V着上A（如图10，b），就是我的d类H—构形，是可约的。给其下边一个V着上A（如图10，c），可先从顶点8交换A—B链，使图中的A—C和A—D连通链断开，图成为K—构形而可约（如图10，d）。其他的d类（5，6）构形（如图11），若给其上边一个V着上A，本身就是可同时移去两个同色B的K—构形（如图12）。给其下边一个V着上A（如图13），可以先从顶点8交换A—B链，使图中的A—C和A—D连通链断开，图成为K—构形而可约（如图14）。





2、8  d类（5，6）构形，就是把d类（5，5）构形中顶点6和7中间的B色顶点去掉，并使顶点6和7直接相邻，图中的C—D链成为环形链（如图15，a）。给其上边一个V着上A（如图15，b），既是可约的b类H—构形，又是可同时移去两个同色的K—构形。从顶点8交换A—B链，可使交叉且连通的A—C链和A—D链同时断开，使图变成K—构形而可约（如图15，c）。交给其下边一个V着上A（如图15，d），也是既是可约的b类H—构形，又是可同时移去两个同色的K—构形。同样也可以从顶点8交换A—B链，可使交叉且连通的A—C链和A—D链同时断开，使图变成K—构形而可约（如图15，e）。

其他的如图11中的五个对称构形，当去掉顶点6和7中间的着B色的顶点后，也会有同样的结果，也都是可约的。

可见，（5，5）构形和（5，6）构形都是可约的。这无疑对四色猜测的证明是有益的。

雷  明
二○一八得四月二十九日于长安

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

。。。。。。。。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，