仿87651028《Birkhoff钻石构形为可约的证明》，证明（5，5）构形的可约性

雷明85639720

仿87651028《Birkhoff钻石构形为可约的证明》，证明（5，5）构形的可约性
雷  明
（二○一六年元月十四日）

11223344介绍了紫色的博客中转载的87651028的《Birkhoff钻石构形为可约的证明》一文，其中对王树禾证明Birkhoff钻石构形是可约的一段进行了补充说明。另外87651028也从王树禾《图论》书中列出的Birkhoff钻石构形围栏着色可能的三十一种分布中，取了几种对Birkhoff钻石构形的可约性进行了证明。我现在完全按照87651028的证明，也取相同的围栏着色模式，对（5，5）构形的可约性证明如下：

1、设（5，5）构形（如图1）的围栏顶点为a、b、c、d、e、f，再设（5，5）构形的两个待着色顶点为k、m。（5，5）构形与Birkhoff钻石构形都有六个围栏顶点，所以我也认为（5，5）构形的围栏顶点可能的着色模式也与王树禾对Birkhoff钻石构形围栏顶点可能的着色模式分析是相同的，也有31 种（这里就不一一列出了）。下面按87651028的文章对（5，5）构形着色如下：
2、围栏顶点a、b、c、d、e、f分别着色为1、2、1、3、1、3，如图2。不管围栏顶点以外的顶点如何着色，都可直接给k、m分别着上4和2，不需要改动围栏顶点的颜色，如图3。

3、围栏顶点a、b、c、d、e、f分别着色为1、2、3、1、4、3时，如图4。也不管围栏顶点以外的顶点如何着色，都可直接给k、m分别着上4和2，也不需要改动围栏顶点的颜色，如图5。
注意：这种围栏着色的情况下，87651028是没有给Birkhoff钻石构形中的四个待着色顶点着色的。只是说了一句：“因此，证明图5.17（a）是可约的，其工作量还是很大的。”其中图5.17（a）就是指Birkhoff钻石构形。

4、围栏顶点a、b、c、d、e、f分别着色为1、2、1、3、1、4时，如图6。也可以不管围栏顶点以外的顶点如何着色，也都可直接给k、m分别着上3和2，仍然也不需要改动围栏顶点的颜色，如图7。



5、围栏顶点a、b、c、d、e、f分别着色为1、2、3、1、2、3，如图8。一眼可以看出k可以着4，剩下的便是一个以m为中心顶点的5—轮构形，如图9。若在围栏顶点外存在着与赫渥特图同样的两条连通的相交叉链4—1和4—2，并存在着a、b、d、e的1—2环形链时（如图10），这是一个标准的赫渥特“九点形”图。从两相交的连通链的相交顶点w（或者k）对3—4链进行交换，都可构形变成一个非渥特构形（如图11和图12）。这两个图（图11和图12）都是可以再进行一次交换，就可以给待着色顶点m分别着上4（或2、1）和3（或2、1）的（如图13和图14）。当然也可以象张彧典老师一样，采用赫渥特颠倒的方法进行着色。

   这里要说明一点的是：87651028在这里对Birkhoff钻石构形可约性的证明中，并不是采用了与我上面采用的有两条相交叉的连通链的赫渥特构形，而是采用了一个比赫渥特构形更好着色的非赫渥特构形的图。他也在围栏顶点外增加了一个顶点w，也形成了两条相交叉且连通的链。但这两条交叉链并不是赫渥特图中那样的交叉链，所以说它是一个非赫渥特构形的图。并且87651028也是先对Birkhoff钻石构形的四个待着色顶点一个一个的进行着色的，他首先对其中的三个待着色顶点k、s、t进行了着色，而最后只剩下一个待着色顶点m，仍是一个以m为中心的5—轮构形（如图15）。
6、87651028对围栏顶点a、b、c、d、e、f分别着色为1、2、3、1、2、3的情况的着色：

    图15和图16是完全根87651028所说做法画出来的。他说：“在围栏顶点 abcdef 着 123123 色时，在围栏外设一顶点 w 并着 4 色。(1) 使顶点 w 分别与顶点 ab 连接实线，而分别与顶点 de 连接虚线。再分别给顶点 kst 着 442 色（如图15——雷明注）。(2) 这样，在新形成的图 G 中，顶点 kbwe 与顶点 kawd 有相交的 4-2-4 和 4-1-4 二色链。(3) 只要把顶点 bc 所着的 23 色改为 32 色，可给顶点 m 着 3 色（如图16——雷明注），则图 G 为 4-着色的，是可约的。” 所谓的新图G中有两条相交的连通链，实际上对于以m为中心的5—轮构形来说，只存在顶点k到d的连通链1—4，从顶点c开始对1—4链的相反链2—3进行交换，也就是“把顶点 b、c 所着的 2、3 色改为 3、2 色”，这时顶点m周围已没有了着3色的相邻顶点，给m着3当然是可以的。
但87651028随后却说：“另外说明一点，在以上这种情况时，不能证明Wernicke定理中（5，5）构形是可约的。”大家看一看，又是关键的时候他就只用一句话代替，塘塞过去了。为什么不说明为什么 “在以上这种情况时，不能证明Wernicke定理中（5，5）构形是可约的。”呢。你那个Birkhoff钻石构形中有四个待着色顶点，着色难度一定更大一些，都可以4—着色，而这个（5，5）构形却只有两个待着色顶点，着色难度相对的还会小一些，为什么就不能证明其是可约的（即是可4—着色的）呢。这就是这些数字先生的贯用手法，只说“不”，而不说“为什么不”，他们没有一次里指出过别人的具体问题所在。因为他们本身就是稀里糊涂的，完全是按书本上说话，他们哪里能看出别人的具体问题嘛。
有些人说，要证明一个构形是可约的，心须把围栏顶点所有的各种着色情况都考虑完，看其待着色顶点是否都可着上四种颜色之一。87651028的证明，是不是能说明Birkhoff钻石构形就是可约的呢，完全不能。因为他在“围栏顶点a、b、c、d、e、f分别着色为1、2、3、1、4、3时”，他只说了工作量很大，但并没有具体给Birkhoff钻石构形的四个待着色顶点着色（也可见了后面的附录）。所以也不能说他就证明了Birkhoff钻石构形是可约的。
7、用87651028的这种方法能不能证明（5，5）构形是可约的呢，我们来试一下：
按87651028所说的去做，“在围栏外设一顶点 w 并着 4 色。”得到图17。(1) 使顶点w分别与顶点a、b连接实线，而分别与顶点d、e连接虚线（其实用不用虚线都是无所谓的，既然87651028要求用虚线，我也就用虑线）。再给顶点k着4色。这时图就成了一个可以同时移去两个同色的非赫渥特构形。(2) 这样，在新形成的图 G 中，顶点 k、b、w、e 与顶点 k、a、w、d 有相交的4—2—4和4—1—4二色链（如图17）。(3)只要把顶点 b、c所着的2、3色改为3、2色，并把顶点a、f所着的1、3色改为3、1色。这时m的相邻顶点中没有了3色，把3给m着上即可（如图18）。这怎么能说“在以上这种情况时，不能证明Wernicke定理中（5，5）构形是可约的”呢。

8、以上我还漏掉了两种围栏顶点着色是“1、2、1、3、4、3和1、2、1、2、1、3的情况，现在补上。

①　围栏顶点着色是1、2、1、3、4、3的情况，如图19。这个图一眼就可以看出来k可以着4，m可以着2的（如图20），仍与围栏顶点外的顶点的着色是没有关系。
②　围栏顶点着色是1、2、1、2、1、3的情况，如图21。也是一眼就可以看出k可以着4，剩下来的也是一个以m为中心的5—轮构形，如图22。如果要把这个图变成一个赫渥特图型的H—构形时，图中就得有顶点d到k的连通链2—4和顶点d到f的连通链2—3，还要有经过顶点k和f的环形链3—4，但作图的结果说明，图22是不可能变成H—构形的。因为若要变成H—构形，图中便出现了交叉边（如图23，图中画圈处就是交叉边）。只要不出现类似赫渥特图的H—构形，不管其围栏顶点间有何等的链，都是可以空出颜色来给待着色顶点m着上的。这已是坎泊早在一百多年前就已经证明了的。


9、六边形围绕栏顶点的31种着色情况不，87651028只选择用了以上的1、2、1、3、1、3，1、2、3、1、4、3，1、2、1、3、1、4，1、2、3、1、2、3，1、2、1、3、4、3，1、2、1、2、1、3六种，其中1、2、3、1、4、3的一种情况，87651028还没有对其待着色顶点进行着色。不知该说87651028和王树禾的结论应是Birkhoff钻石构形是可约的呢，还是不可约呢。
若是可约的，那么我这里仿他们的方法对（5，5）构形进行的证明，也应说明（5，5）构形是可约的。因为在所选用的围栏顶点着色的六种情况中，87651028至少还有一种没有对Birkhoff钻石构形的待着色顶点进行着色，而我却在六种情况下都对（5，5）构形的待着色都进行了着色。
10、看来，王树禾与87651028对Birkhoff钻石构形可约性证明的方法我认为都是不合适的，让构形中有多个待着色顶点的做法也是不应该的，用（5，5）构形和（5，6）构形等来代替5—轮构形的做法也就不对了。还是应回到直接研究5—轮构形是否可约的正规轨道上来吧。不要再想歪门邪道了。

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

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

附：紫色（转载）的87651028的《Birkhoff 钻石构形为可约的证明》一文
1。对于王树禾《图论》（网址） 图5.17(a) 为可约的证明，R.Wilson 在 Four colors suffice （四色就够了）第159-163页，有论述。这里，简介如下：
2。王树禾《图论》第100-101 页的“设 T 是 4CC 的最小反例，…… 123434 ”这些内容，应该作为本证明的开始。然后，再往下进行。
3。先设《图论》的 图5.17(a) 中间 4 个顶点，从最上边那个顶点起，按顺时针方向，依次为 kmst，再给图5.17(b) 的围栏顶点 abcdef 分别着 121313 色。(1) 在顶点 ec（或者顶点 ea）之间有 1-4-1 二色链时，可把顶点 d（或者顶点 f）所着的 3 色改着为2 色。这时，围栏顶点已着 121213 色，顶点 kmst  可分别着 4342（或者 4243）色，则图 5.17(a)为 4-着色的。(2) 在顶点 e 与其它顶点无 1-4-1 二色链时，可把顶点 e 所着的 1 色改着为 4 色。这时，围栏顶点已着 121343 色，顶点 kmst 可分别着 3412 色，则图5.17(a) 为 4-着色的。
4。对以上这些，《图论》在第 101 页上介绍得太简略了。它只是说，要把坏着色 121313 转换为好着色121343 或 121213，只要把 Kempe 链上的 1与4 或 2与3 互换即可。
5。为什么说，着色 121213 是“好着色”，而着色 121313 却是“坏着色”呢？(1) 在围栏顶点 abcdef 着 121213 色时，可直接给顶点 kmst 着4342（或者4243）色，见图5.18，故称着色 121213 为好着色。(2) 在围栏顶点 abcdef 着 121313 色时，不能直接给顶点 kmst 着 4 色。例如，在给顶点 kmt 分别着 324 色后，而顶点 s 则无法着 4 色中的某一色。只有在将其转换为着 121213  色之后才行，故称着色 121313 为坏着色。
6。顶点 abcdef 还要着其它方式的 4 色，例如着 123143 色，可见《图论》第 100-101 页。因此，证明图5.17(a) 是可约的，其工作量还是很大的。
7。例如，在围栏顶点 abcdef 着 121314 色时，(1) 在顶点 fd 之间有 3-4-3 二色链时，可把顶点 e 所着的 1 色改着为2 色。这时，顶点 abcdef 已改着为 121324 色，顶点 kmst 可分别着 4213 色，则图5.17(a) 为 4-着色的。(2) 在顶点 fd 之间无 3-4-3 二色链时，可把顶点 f 所着的 4 色改着为 3 色。这时，顶点 abcdef 又着 121313 色，还得再进行着色转换，使之改着为 121213 色。
8。再如，在围栏顶点 abcdef 着 123123 色时，在围栏外设一顶点 w 并着 4 色。(1) 使顶点 w 分别与顶点 ab 连接实线，而分别与顶点 de 连接虚线。再分别给顶点 kst 着 442 色。(2) 这样，在新形成的图 G 中，顶点 kbwe 与顶点 kawd 有相交的 4-2-4 和 4-1-4 二色链。(3) 只要把顶点 bc 所着的 23 色改为 32 色，可给顶点 m 着 3 色，则图 G 为 4-着色的，是可约的。 另外说明一点，在以上这种情况时，不能证明 Wernicke 定理中的（5-5）构形是可约的。
9。Four colors suffice 书，现在 （网址）网上可邮购。想深入了解其内容者，可买来看看。
    -- 网友“87651028”写于 2015-10-18。  

雷明85639720

,,,,,,,,