不可避免构形着色法证明四色猜测的基本原理

雷明85639720

不可避免构形着色法证明四色猜测的基本原理
雷  明
（二○二三年十一月二十四日）

1，平面图着色是一个顶点接着一个顶点的着，总存在着一个最后要着色的待着色顶点。把这种还有一个顶点未进行4—着色的图就叫做构形，与待着色顶点相邻的顶点叫围栏顶点。围栏顶点占用颜色数小于等于3时，待着色顶点可以直接着上四种颜色之一，是终局构形，着色结束。围栏顶点占用颜色数等于4时，待着色顶点不能直接着上四种颜色之一，需要对部分已着色顶点的颜色进行调整，使围栏顶点占用的颜色数减少下来，才能给待着色顶点着上四种颜色之一。这种构形叫困局构形。
2，由于平面图的顶点平均度是小于6的，所以任何平面图中可以不含大于等于6度的顶点，但不能没有小于等于5度的顶点。这就是说，任何平面图中大于等于6度的顶点是可以避免的，而小于等于5度的顶点是不可避免的。这就决定了着色时总可以把构形的待着色顶点放在不可避免顶点之上，成为不可避免的构形。这就把一个研穷对象（即待着色顶点的度）是无穷的问题转化成了有穷问题了。不可避免构形中除了终局构形外，可构成困局构形的顶点就只有4度和5度顶点了。
3，把用两种颜色交替对顶点着色的道路或树叫做色链（简称链，也叫坎泊链），交换链中各顶点的颜色，可以达到改变链中任何一个顶点颜色的目的。这种交换叫坎泊交换或叫坎泊链法。困局构形的某对对角围栏顶点间没有连通链时，可以从一个对角顶点开始，对由该顶点的颜色与其对角顶点的颜色构成的色链进行交换，使该顶点的颜色变成与其对角顶点相同的颜色，围栏顶点所占用的颜色就会减少一种。把减下来的一种颜色给待着色顶点着上，问题也就解决了。这种构形叫做K—构形，坎泊在1879年早就已经解决了。而把不能用坎泊链法从围栏顶点中空出任何一种颜色的构形叫H—构形。H—构形是赫渥特在1890年发现的，也是坎泊证明中所遗漏了的整个一类构形。
4，H—构形只所以用坎泊链法不能从围栏顶点中空出任何一种颜色，主要是因为该类构形中含有双环交叉的A—C链和A—D链，不但不能移去A，C，D三色之一，且不能连续的移去两个同色B。看来，要解决这类构形的问题，必须破坏双环交叉链，使构形转化成K—构形。
5，要破坏双环交叉链，就必须使以下四个关键顶点中的任何一个顶点的颜色发生改变。这几个关键顶点分别是：两链的共同起始顶点（着A）和交叉顶点（着A），以及两链的两个末端顶点（分别着C和D）。在含有经过了A色关键顶点的A—B环形链的条件下，交换经过了两链的两个末端顶点C和D的C—D链，或在含有经过了两链的两个末端顶点的C—D环形链的条件下，交换经过了任一A色关键顶点的A—B链，都会使有关的关键顶点的颜色发生变化，原有的双环交叉链断开，构形转化成K—构形。这种构形叫做有环形链的H—构形，这种交换方法叫做断链法。
6，那么，不含有A—B环形链和C—D环形链的无还形链的H—构形如何解决呢？既然不能连续的移去两个同色B，那么就先移去一个B，使构形的类型由原来的BAB型变成CDC型或DCD型，再看新的构形是否转化成了K—构型或含有环形链的H—构形。若是，问题也就解决了，若不是，可以继续进行同方向的连续转型。可以证明在有限的40次转型之内，一定可以转化成可以连续的移去两个同色的K—构形或是含有环形链的H—构形的（证明略，可参见其他文件）。
7，这就是用有限数量的不可避免构形代替无穷多的任意平面图，用着色的方法对四色猜证明的基本原理。结论是四色猜测是正确的。
8，有环形链的H—构形可以通过改变环形链上某些顶点的办法转化成无环形链的H—构形，但这一过程是不可逆的，所以无环形链的H—构形是不能直接转化成有环形链的构形的。因此，无环形链的H—构形只能是通过转型法进行解决。

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

雷明85639720

，，，，，，，，