5—轮构形中4种颜色、6条色链的组合分析及四色猜测的证明

雷明85639720

5—轮构形中4种颜色、6条色链的组合分析及四色猜测的证明
雷  明
（二○一六年二月四日）

5—轮构形中除了中心顶点（待着色顶点）未着色外，其他5个轮沿顶点占用完4种颜色的着色情况，只能是有一种颜色用了两次，别的3种颜色分别只用了一次的一种情况，如图1。图中数字表示顶点名称，字母表示颜色种类。下面再定义几个术语。

    1、几个专业术语
色链——由两种颜色构成的一条道路叫色链，简称链。四种颜色所能构成的色链，只能有六种。图1中A、B、C、D四种颜色构成的六种色链分别是A—B、A—C、A—D、B—C、B—D、C—D。
对角链——由5—轮的对角顶点的颜色构成的色链叫对角链。如图1中可能构成的对角链是A—C、A—D、B—C、B—D。
邻角链——由5—轮的相邻顶点的颜色构成的色链叫邻角链。如图1中可能的邻角链是A—B、C—D、B—C、B—D。可见B—C、B—D两链既可是对角链，也可是邻角链。
连通链——对角链在两个对角间是相通的一条链叫连通链。图1中A—C、A—D、B—C、B—D四链都可能成为连通链。
环形链——邻角链构成了一条回路或圈时叫环形链。图1中A—B、C—D、B—C、B—D四链都可能成为环形链。
环（或圈）——连通的对角链与5—轮构形的待着色顶点构成的回路叫环（或圈）。图1中A—C、A—D、B—C、B—D四链都可能与待着色顶点V构成环（或圈）。
相邻链——两链中有一种颜色是相同的色链叫相邻链。如图1中的A—C和A—D两链，B—C和B—D两链各都是一对相邻链。相邻链由于有相同的颜色，所以两相邻链可以有同一个起始顶点，中途也可以有相同的顶点，即交叉顶点，可以相互穿过。所以两相邻链可以都是连通链，也都可与待着色顶点V构成环。
相反链——两链中两种颜色都不同的色链叫相反链。如图1中的A—C和B—D两链，A—D和B—C两链，都各是一对相反链。相反链由于两种颜色均不同，所以不会有相同的起始顶点，也不会有相交顶点和相互穿过。所以两相反链是不会同时都连通的，也不会同时都与待着色顶点V构成环的。
相交链——两条相邻链因有相同的颜色，所以它他可以互相穿过，这叫相交链。只有相邻链是可以相交的链。
2、六种链的相互组合分析
①　有两条相交叉链的基本模型
两相邻的连通链只有一个起始顶点是相交顶点的情况，坎泊早已证明是可约的，这里也就不再说了。这里主要说一说两相邻的既有起始顶点是相交顶点，中途又有相交叉的顶点的这种情况，如图2。图中两条相邻链A—C和A—D，既有同一起始顶点2A，又有交叉顶点8A。这种图由于A—C和A—D链分别是连通的，所以不能进行交换，也不能空出A、C、D三种颜色之一给待着色顶点V。现在就只能看颜色B能不能空出来了。

②　可以同时移去两个同色的K—构形

图2情况下，A—C和A—D链的相反链B—D和B—C均是不可能连通的，能不能进行交换和空出颜色，下面进行分析。这一情况下的图若是三角剖分图（极大图）时，可能有以下几种情况：如图3、图4、图5和图6。图3中有一条环形的邻角链A—B，分另一邻角链C—D为环内环外两部分；图6中有一条环形的邻角链C—D，也分另一邻角链A—B为环内环外两部分；图4和图5则都没有环形链，两条邻角链A—B和C—D都是一条道路（直链）。但图3、图4和图5都可同时移去两个同色B给待着色顶点V，都是属于可约的K—构形。而只有图6无论怎样交换，都是不能同时移去两个同色B的构形，它与赫渥特图有相同的特点，所以我们把它叫做H—构形。
③　H—构形的着色方法
图6就是一个H—构形，是由赫渥特图简化而来的“九点形”。由于图中有环形的邻角链C—D，分邻角链A—B为互不相通的两部分，我们交换其中任一部分A—B链，都可以使图变成一个不存在两条连通链、且有交叉顶点的K—构形，再通过一次交换后，可以给V着上A、C、D三种颜色之一。
④　M—构形的着色方法

图3中有一条环形的邻角链A—B，图6中有一条环形的邻角链C—D，现在要问，有没有这两条邻角链A—B和C—D都是环形链的构形呢。回答是，有。这就是米勒构造的米勒图，也叫M—构形，如图7（这是米勒的画法，图中不显示待着色顶点V）。图中的邻角链A—B和C—D都是两条，各有一条环形的，也还有一条直链，两条环形的A—B和C—D链是相互包含的，即相当于一个圈中套着一个圈一样，且两个圈没有共同的顶点。
在M—构形中交换任何一条A—B邻角链都是无用的，图仍然是一个M—构形的图。但交换了任一条C—D邻角链却可以使图变成不存在两条连通链、且有交叉顶点的K—构形，再通过一次交换后，则可以同时移去两个同色B给V着上。
⑤  Z—构形的着色方法
现在还要问，在不能同时移去两个同色B的情况下，还有没有两种邻角链A—B和C—D都不是环形链的情况呢，回答也是“有”。这就是张彧典先生构造的第八个构形一类的图，我把该构形的顶点数尽量减少，又把图变成左右对称的图，得到如图8（这是张彧典先生的画法，5—轮位于图的最下方）。

    图8中的相交叉的两对角链A—C和A—D均是连通的不能交换；两条邻角链A—B和C—D又都是直链，且只有一条，谁也没有把谁分隔成两部分，交换后也不起任何作用；两条相邻的对角链B—C和B—D虽都不是连通链，但却不管是交换一条，还是交换两条，都只能移去一个B，而不能同时移去两个B。怎么办，我们们可以想办法。既然不能同时交换两个关于B的链，不能同时移去两个同色B，那么我们就只交换一个关于B的链，先移去一个同色B，使构形发生变化。的确，无论交换那一条关于B的链，都可以使构形由Z—构形转化为可以同时移去两个同色的K—构形或H—构形。上面已经说了，K—构形和H—构形都是可以4—着色的，都是可约的，那么这个Z—构形也就是可以4—着色的，也是可约的。
3、四色猜测的证明
还有没有别的5—轮构形呢，没有了。上面我们分析的由5—轮轮沿顶点中的三个单色组成的相邻链A—C和A—D是连通的、且是相交叉链的情况，是有连通链情况的最复杂的情况，在此情况下，又分析了两种邻角链A—B和C—D是不是环形链的四种情况，分别是：① A—B链是环形链，C—D链不是环形链；② C—D链是环形链，A—B链不是环形链；③ A—B链和C—D链两条都是环形链；和④ A—B链和C—D链两条都不是环形链的四种情况。在这四种情况下的构形都是可以4—着色的，都是可约的。且再也不可能有别的情况的构形出现了。因此，也就证明了所有含有两条相邻的连通且相交叉的对角链的5—轮构形都是可约的。再加上一百多年以前坎泊已证明是可约的构形，就可以说平面图所有的不可免构形都是可约的，当然也就证明了四色猜测是正确的。
雷  明
二○一六年二月四日于长安

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

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，，，