围栏顶点已占用完四种颜色是证明某构形是否可约的先决条件

雷明85639720

围栏顶点已占用完四种颜色是证明某构形是否可约的先决条件
——论王树禾《图论》书中证明伯克豪无钻石构形可约性的错误
雷  明
（二○一五年十月二十七日）

    1、围栏顶点已占用完了四种颜色是证明一个构形是否可约的先决条件。一个构形是否可约，证明时不但要考虑到围栏顶点及其以外的顶点是4—着色的，还要假定围栏顶点已占用完了四种颜色。在这种情况下，待着色顶点能着上图中已用过的四种颜色之一，则该构形就是可约的；否则就是不可约的。只有当平面图所有的不可免构形都是可约的时，才能证明四色猜测是正确的。
2、王树禾教授的《图论》书中证明伯克豪夫钻石构形时，虽然考虑了围栏顶点占用完四种颜色的情况，但具体证明时，只证明了围栏顶点占用了三种颜色的情况，没有证明围栏顶点占用完了四种颜色的情况，应该说是不完善的，或者说是错误的。因为他没有证明围栏顶点占用了四种颜色时，其待着色顶点是否可以着上图中已用过的四种颜色之一。由于围栏顶点没有占用完四种颜色，所以也就不可能存在围栏顶点外有两条交叉的连通链的最复杂的情况，这就绕过了证明5—轮构形的难点所在，因此我一直认为是不能用别的构形来代替5—轮构形的。虽然王教授得到的结论说该构形是可约的是正确的，但也不能说明他的方法也是正确的。如果在证明时围栏顶点可以不要占用完四种颜色，那么伯克豪无钻石构形的六边形围栏顶点也可以只用两种颜色着色，可为什么王教育授在证明时该构形是可约的时，所列举的六边形围栏顶点可能的“色分布”的模式却没有只占用两种颜色的情况呢。
3、如果给伯克豪夫钻石构形六边形围栏顶点abcdef分别着以121212当然也是可以的，这时待着色顶点kms分别着以434，剩下了一个待着色顶点t不能着上四种颜色之一，如图1，a。但这时的构形就是一个以顶点t为待着色顶点的5—轮构形，且该轮的5个轮沿顶点已用完了四种颜色，其中4是用了两次的。这不还是只有一个待着色顶点的构形吗。我们现在设在这个5—轮构形的围栏顶点外存在两条交叉的连通链3—1和3—2，但这两条链是不可能实际交叉的，而只能是除有共同的起始顶点外，中途还有一个共同的顶点。该构形也可以同时移去两个同色4，把4给待着色顶点t着上即可。这就证明了伯克豪夫钻石构形是可约的。

4、在11月27日11223344重新发的新贴子《（文献介绍）有关四色问题电脑证明的资料！》（网址是：  该贴的内容主要是介绍《紫色的博客》（网址是：  ）里的文章。该博主新转载了87651028写于10月18日的文章《Birkhoff 钻石构形为可约的证明》，文章中说王树禾教授在《图论》书对该构形的证明“介绍得太简略了”，因此他又祥细的说了一次。他说给：“围栏顶点abcdef分别着121313色”。“在顶点e和c之间有1—4—1二色链时，可把顶点d所着的3色改着为2色。这时，围栏顶点已分别着121213色，顶点kmst可分别着4342色”，则该项构形“为可4—着色的”，也即可约的。如图2。

请问，为什么不直接先给待着色顶点ats着上424，再考虑m能不能着上图中已用过的四种颜色之一呢，如图3。这时的图已经是一个以顶点m为待着色顶点的5—轮构形，该5—轮构形的围栏顶点以外只可能存在两条有同一起始顶点的、另外还有一个公共顶点（着色2）的连通链2—1和2—3（这一着色为2的公共顶点只是两链共用，而两链在此并没有实际意义上的“交叉”），该构形可以同时移去两个同色4，把4给待着色顶点t着上即可。这也就证明了伯克豪夫钻石构形是可约的。

5、87651028在说明说abcdef分别着121313为什么是是坏着色时又说：“在围栏顶点abcdef着121313色且不变时，不能直接给顶点kmst着4色（这里说得很不明白，似乎应该说成是“不能直接给顶点kmst都着4色之一”。——雷注）。例如，在给顶点kmt分别着324色后，顶点s则无法着4色中的某一色”如图4，a。请问这不又是一个以顶点s为待着色顶点的5—轮构形吗。按87651028所说：“只有在将其转换为121213色之后”，才能把kmst着上已用过的四种颜色之一，也只能是图2中的结果，“故称着色121313为坏着色”。
但从图4，a中可以看出，图中有一条环形的1—3链，无论以顶点s为待着色顶点的5—轮构形围栏顶点外的顶点如何着色，2—4链都一定是被这条1—3环形链分隔成环内环外两个互不连通的部分的。如果5—轮构形围栏顶点外有两条连通的且相交叉的链1—2和1—4，则交换处于环形链1—3环内的那条由顶点m—t构成的2—4链，可使1—4链变成不连通的（即断开），此时图中仍有一条连通的2—4链（如图4，b）。这时，再从顶点m或顶点e交换1—4链，就可空出颜色1或4给待着色顶点s着上，如图4，c和图4，d。这也能够证明伯克豪夫钻石构形是可约的。
  
6、《紫色的博客》的博主在转载87651028的文章时，增加了最后所举的一个例子，说：“在围栏顶点abcdef着 121314 色时，(1)在顶点f和d之间有3—4—3二色链时，可把顶点e所着的1色改着为2色。这时，顶点abcdef已改着为121324色，顶点kmst可分别着 4213色”，如图5。则该构形“为4—着色的”。如果先不把顶点e由1色改着2色，而把顶点kmt分别着以423，则顶点s就是一个5—轮构形的待着色顶点。这个5—轮构形围栏以外的顶点是不可能存在两条实际“交叉”链的，而只可能存在两条有共同起始顶点且中途又有共同顶点的链2—1和2—4，这样的构形，是可以同时移去两个同色3的，如图6。也可以说明伯克豪夫钻石构形是可约的。


接着博主又说：“(2)在顶点f和d之间无3—4—3二色链时，可把顶点f所着的4色改着为3色。这时，围栏顶点abcdef又着121313色，还得再进行着色转换，使之改着为121213 色等。（转载时，增加了第 5 部分内容等）。”既然可以直接把顶点f由4色改为3色，那么在这种情况下当然也可以直接把顶点e由1色改为2色，给顶点kmst分别着上4213就可以了，如图7。为什么非得要先改f4为f3，又要走把abcdef先变成121313，再变成121213，再走图2的老路呢。


7、以上笔者对伯克豪夫钻石构形的可约性证明，都是在5—轮构形下进行的，也都只有一个待着色顶点。能过证明可以看出，用以代替5—轮构形的构形，最后着色还都要按5—轮构形来处理，也只有一个待着色顶点。所以说，不能用任何别的构形来代替5—轮构形，也是代替不了的。一个构形只有一个待着色顶点。

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

雷明85639720

，，，，，，，，，