R—构形（5—轮构形）的可约性证明

雷明85639720

R—构形（5—轮构形）的可约性证明
雷  明
（二○一五年十一月二日）

所谓R—构形是张彧典先生对5—轮构形的叫法，我在这里也就这样提及了。R—构形是可约的，实际上已由很多的爱好者用不同的方法已经证明了。但由于爱好者不是专业的，无专业人员给以评审和鉴定，以致其研究成果总不能得到大家的承认。我今天仿照大家习惯的着色方法来对R—构形进行可约性的证明。
1、王树禾教教授《图论》书中的原文：
我现在把大家看习惯了的王树禾教授在他的《图论》书中对于证明4—轮以下的构形（即张彧典先生的Q，P等构形）的原文全部抄录如下，以对比我后面的证明是否与他的方法相同。
王教授的原文是：
“若四色猜想不成立，我们取得一个反例，它具有最少的顶数。如果他不是三角剖分，我们可以加边，使其成为三角剖分T，而其顶数不变；每个比T顶数少的平面图皆四色的，而T不是。”

“如果T只含图5.11的（a）或（b）这种构造，则删除顶点v之后， （T－v）≤4。由于v的邻顶至多3个，所以可以把与v相邻的顶相异的第四种颜色给v染上，于是 （T）≤4，与T是反例相违，于是T中不含对构（a）与（b）。”
“若T含对构（c），这时我们不能立刻对顶v染色。为了克服这一麻烦，Kemple采用了一种巧妙的证法（现称Kemple链证法），证明我们可以对T－v的上色进行变更，使得要么a与c要么b与d有相同的颜色。于是对v可以上色，使得T是四色的，从而得到矛盾。为了实际得到上述结论，设a，b，c，d分别染上红、绿、蓝和灰四种颜色，图T－v可能找到从a到c的轨，其顶仅是红的与蓝的（称为Kemple链），也可能找到从b到d的一条轨，其上的顶不是绿色就是灰色，但是这两条轨不能同时存在，因为如果同时存在，那么它们的公共点是何种颜色呢？是红色或蓝色，同时又应是绿色与灰色，这是不可能的。不失一般性，不妨设不存在从a到c的红—蓝轨，这时容易看出，我们可以交换颜色，使T－v中a顶变成蓝色而b，c，d三顶不变色，于是可以对v顶着以红色，使得T呈4色，矛盾。”

“因此Kemple证明了T不含图5.11中的（a）（b）（c）的结构。如果他还能证明T不含结构（d），则他的证明则可彻底完成，因为T中应含（a）（b）（c）（d）四种结构至少一种。可惜Kemple在讨论第四种情况（d）时，出现了证明错误！”
“1890年Heawood指出了Kemple证明的漏洞，Heawood沿用Kemple的证明方法证明出了一个较弱的结论，用五种颜色可以对平面图正常顶点着色，即 （平面图）≤5，称为五色定理。”
2、R构形的可约性证明：
R—构形，即图5.11中的（d）结构的5—轮构形，是否可约，是否可使得T呈4色，我们现在开始证明：
若T中含有结构（d），我们把（d）中v的5个相邻顶点用1，2，3，4，5表示（代替王树禾书中的a，b，c，d，e），用A，B，C，D分别代替王树禾书中的红，蓝，绿，灰四种颜色，当（d）中v的5个相邻顶点点用完了A，B，C，D四种颜色时（如图1），如何给v着上图中已用过的四种颜色之一呢？

    该构形5—轮的对角顶点间没有连通链（链是用两种颜色相间着色的道路）以及只有一条连通链的情况，这早在1879年由坎泊已经证明了是可约的。现在我们主要只研究5—轮的对角顶点间有两条连通链的情况。
（1） 有两条相邻链（我们把有一种共同颜色的两条链叫相邻链）的情况，如图2。图2，a是有两条对顶链（两链是同一个起始顶点的链，中途没有共同的顶点），连通的A—C和A—D链分别把B—D和B—C链隔断，不可能再成为连通链。所以两次交换关于两个同色B的链，即可空出B给v着上。先从那个顶点起交换都是无所谓的。于是有 （T）≤4，与T是反例相违，于是T中不含“有两条对顶链的（d）结构”； 图2，b是有两条交叉链（两链的起始顶点不同，但中途又有共同的顶点，产生相交叉情况），连通的B—C和B—D链分别把A—D和A—C链隔断，不可能再成为连通链，所以从顶点4交换A—D链，或从顶点5交换A—C链，可分别空出D或C，给v着上D或C。于是也有 （T）≤4，也与T是反例相违，所以T中也不含“有两条交叉链的（d）结构”；


（2） 有两条既对顶又交叉的链的情况，如图3。这种情况，看来似乎是可以分别从顶点1可以交换B—D链，从顶点3可以交换B—C链，都可以移去B。但由于B—D链可以穿过A—D链，交换后可能会产生从顶点3到顶点5的B—C连通链，使得不能同时移去两个B（如图4，a）。同样的，B—C链可以穿过A—C链，交换后可能会产生从顶点1到顶点4的B—D连通链，使得也不能同时移去两个B（如图4，b）。当图4中的两种情况都不出现时，可以同时移去两个B，构形可约；当只有一种情况可能出现时，可以有选择性的先从不会生成另一个关于B的连通链的B顶点开始交换关于B的链，再从另一个B顶点开始交换另一个关于B的链，也可同时移去两个B，构形也是可约的。但当两种情况都出现时，这种结构的（d），着色还是有一定的难度的。


但我们发现，在这一情况下的图中，左右两边各有四个顶点对角用了相同的颜色（如图5，a中为加大了的顶点），在要构成极大图（极大图的面都是三角形面）时，四顶点中间至少还存在着一个顶点，着上不同于原两种颜色的另一种颜色。
第一，若给左边的那四个顶点中间的顶点着D色，给右边的那四个顶点中间的顶点着C色，则图中就产生了一条C—D环形链（如图5，b这就是赫渥特图型的构形），把A—B链分成了环内环外互不连通的两部分，交换其中任一部分A—B链，都可以使原来的两条既对顶又交叉的连通链断链（我们给赫渥特图着色时也是这样处理的），如图6。再进行一次坎泊的颜色交换，图6，a就可以空出A，C，D三色之一给v着上，图6，b就可以空出B，C，D三色之一给v着上。于是仍有 （T）≤4，与T是反例也相违，于是T中不含“有两条既对顶又交叉的链，且含有C—D环形链的（d）结构”；


第二、若给左右两边的那四个顶点中间的顶点都着A，则图中就可能产生一条环形的A—B链（如图7），把C—D链分成了环内环外互不连通的两部分，交换其中任一部分C—D链，都可以使原来的两条既对顶又交叉的连通链变得实际上的不交叉（只是中途有一个共同的顶点，两链并没有真正的交叉），如图8。两图均再进行一次坎泊的颜色交换，都可以空出A，C，D三色之一给v着上。于是仍有 （T）≤4，与T是反例也相违，于是T中不含“有两条既对顶又交叉的链，且含有A—B环形链的（d）结构”；
第三、若给一边的那四个顶点中间的顶点着D（或C），给另一边的那四个顶点中间的顶点着A，则图中就不再存在任何的环形链，而只是两条直的A—B链和C—D链，如图9，a。这与张彧典先生的第八构形基本相似。


这种情况下，A—C链，A—D链，B—C链，B—D链都不能交换，交换了A—B或C—D也只相当于把图中所有的A点和B点交换一次，把所有的C点和D点交换一次，不起什么作用。似乎由四种颜色所能够成的六种链都不能交换，但我们可以考虑只交换一个关于B的链，而不交换另一个关于B的链，使5—轮的5个轮沿顶点中用了两次相同颜色的顶点的位置发生变化，且所用的颜色也发生变化，这一点一定是能够办到的。这就是张彧典先生所说的“难点转化”。所用的交换方法就是张彧典先生的“赫渥特颠倒”。
对图9，a从顶点1交换B—D链得到图9，b，这个图有两条既对顶又交叉的连通链C—A和C—B，同样也不能同时去两个同色D，但图中却有一条环形的A—B链，把C—D链分成了环内环外互不连通的两部分（这又是一个赫渥特图型的图），交换任一部分C—D链，都可以使原来的两条既对顶又交叉的连通链断链，如图10。再进行一次坎泊的颜色交换，图10，a就可以空出A，B，C三色之一给v着上，图10，b就可以空出A，B，D之一给v着上。于是仍有 （T）≤4，与T是反例也相违，于是T中不含“有两条既对顶又交叉的链，但不任何环形链的（d）结构”。当然对图9，a从顶点3交换B—D链，同样的会得到T中不含“有两条既对顶又交叉的链，但不任何环形链的（d）结构”的结

现在我们已经分析了R构形的各种结构，证明了结构（d）是可约的。于是对于（d）仍有 （T）≤4，与T是反例也相违，于是T中不含（d）结构。
3、四色猜测测是正确的：
由于R构形是可约的，所以王树禾教授《图论》书中的图5.11中的结构（a）（b）（c）（d）四个构形就都是可约的了。由于这四个构形都是极大图中的不可免构形，所以说，到此就可以说四色猜测得到证明是正确的。


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

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

雷明85639720

，，，，，，，，，，