1、证明四色猜测时离不开5—轮构形
1879年坎泊证明四色猜测时,漏掉了一种情况的构形,在1890年让赫渥特构造了出来。尽管赫渥特图从现在来看是能够4—着色的,但含有赫渥特图型的5—轮构形至少在1990年以前仍是无法证明其是否可约。1904年Wernicke提出了用(5,5)和(5,6)代替5—轮构形,想把5—轮构形绕开。之后,又有Birkhoff的钻石构形等等,五花八门,一直到阿贝尔的近2000个构形。
5—轮构形已是坎泊早已证明了的,平面图的不可免构形之一。在证明猜测时,能不能绕开它,而用别的什么去代替它呢。我们在前两篇文章《(5,5)不能代替5—轮构形的证明》和《伯克豪夫钻石可约性研究》中,已经证明了是不能绕开5—轮构形的。
对具有多待着色顶点的构形着色,总得一个一个的去给待着色顶点着色,到最后所剩下一个待着色顶点时,仍是一个5—轮构形。特别是我们在上两篇文章中对(5,5)和伯克豪夫钻石的可约性进行研究时,不但常遇到5—轮构形,而且还常遇到赫渥特图型的5—轮构形。所以说,在四色猜测证明时,是不可能离开5—轮构形的,也是不能用任何别的什么来代替5—轮构形的。但赫渥特图型的5—轮构形,既不能同时移去两同色,也不能移去其他三种颜色之一,该如何办呢。
2、四色猜测的证明
是不是赫渥特图型的5—轮构形,就不可约呢,四色猜测就无法再继续证明呢。不是的。我们可以想办法使连通链进行“断链”,使本来连通的链变成不连通的,为“施行坎泊的颜色交换技术,空出颜色给待着色顶点”创造条件。
① 赫渥特图型的5—轮构形中,两条相交叉的A—C和A—D连通链一定有一种颜色A是两链共同都有的,两链的交叉顶点就是这种颜色A。从交叉顶点(着色为A)交换该顶点的颜色A与两链均没有的颜色B组成的链,就可以使两条连通链均“断开”。这时图就变成了不存在任何连通链的坎泊构形,给待着色顶点着上图中已用过的四种颜色之一,是没有问题的。
② 如果原有的连通链已断开,而又产生了两条新的连通且相交叉的链时,则这个构形就是具有赫渥特图特征的敢峰—米勒图型的5—轮构形。这种构形的“断链”就得从两链的非交叉顶点C或D的顶点(如5—轮的轮沿着C和D的顶点)施行两链的非共同颜色C和D组成的色链C—D,也能使原有的两条连通链同时断开,使图变成不存在两条连通链相交叉的坎泊构形,可以同时移去两个同色B。
③ 再若原有的连通链已断开,但仍有另外的两条连通且相交叉的链时,在施行了②中所说的“两链的非共同颜色组成的链”的交换后,仍不能变成坎泊构形时,则这个构形就是张彧典先生的第八构形和雷明先生根据张先生的第八构形所构造出来的那种构形。这种构形就得用所谓的“颠倒”法了。在施行了一次“颠倒”后,一般情况都得到坎泊构形,有时也可能得到赫渥特图型的5—轮构形或敢峰—米勒图型的5—轮构形。然后再用①和②中的方法去解决就得到了坎泊构形。
我们这里的证明,再加上过去坎泊的证明,就能够说明平面图的所有不可免构形都是可约的,四色猜测得到证明是正确的。