“不画图，不着色”证明四色猜测的原理

雷明85639720

“不画图，不着色”证明四色猜测的原理
雷明
（二○一五年五月二十五日）
图的色数γ＝图的最小顶独立集数β＝图的最小完全同态的顶点数α。图的最小完全同态的亏格n同态一定小于等于原图的亏格n原图。图的色数γ大于等于图的密度ω，而小于等于图的密度的一倍半，即ω≤γ≤1.5ω。色数大于图的密度的原因是图中存在着对于某一个最大团来说的不可同化道路，而相互间有联存在的不可同化道路的条数S是受着双重制约的，即S既要不大于密度ω的一半，又要不大于与图同亏格的曲面所能嵌入的最大完全图的顶点数V与图的密度ω的差，即S≤ω/2且S≤V－ω。
1、图中不相邻的顶点可着同一颜色，也可以划分到同一个顶独立集内，还可以同化（把两个不相邻的顶点凝结到一起的过程叫同化）成一个顶点；
2、任何图同化的最后结果都一定是一个完全图，这就叫图的完全同态。而一个图并不只有一个完全同态，如道路P4的完全同态就有两个，一个是K3（把顶点1 和4同化在一起），另一个是K2（把顶点1 和3同化在一起，把顶点2和4同化在一起）。把一个图的所有完全同态中顶点数最少的那一个就叫做图的最小完全同态；
3、同化时，要能够得到图的最小完全同态，就必须遵循一个原则，这就是进行同化的两个顶点间的距离一定要是最小的，即在该两顶点间只能有一个顶点相隔，这样就可以保证所得到的完全同态是最小的，即其顶点数是最少的；
4、图的最小完全同态中的任何一个顶点都是由图中若干个互不相邻的顶点同化而来，它们就构成了一个顶独立集，这些顶点着同一种颜色是完全可以的；
5、图的最小完全同态有几个顶点，这个完全同态着色就得用几种颜色，把这个着了色的完全同态的各顶点，按照同化时的相反方向、连同其已着的颜色一起，再反回到在原图中的位置，一个图的着色就完成了。图中一定不会存在相邻顶点着同一颜色的情况；
6、可以得出结论，图的色数就等于图的最小完全同态的顶点数，求一个图的色数就等于求该图的最小完全同态的顶点数。要证明四色猜测，就相当于只要证明了任意平面图的最小完全同态的顶点数不大于4就可以了；
7、图的亏格是其可嵌入的曲面的最小亏格，那么亏格是n的图一定是可嵌入在亏格为n的曲面上的图。图的同化是在亏格为n的曲面上进行的，最后得到的最小完全同态也一定是嵌入在亏格是n的曲面上的图。比如K5图的亏格是1，其最小完全同态就是原图K5本身，其亏格也应是1；而K3,3图的亏格也是1，但其最小完全同态却是K2，虽然这个K2现在仍是嵌入在亏格为1的曲面上，但K2的亏格却是0（K2不但能嵌入亏格为1的曲面，也能嵌入亏格为0的曲面，小者是0，所以K2的亏格是0）。这就说明图的最小完全同态的亏格一定是小于等于原图的亏格的；
8、假设一个任意图的最小完全同态的亏格是大于原图的亏格的，那么该完全同态可嵌入的曲面的最小亏格就应该比原图可嵌入曲面的最小亏格大，但我们对它的同化仍是在原亏格的曲面上进行的，这时的最小完全同态根本不可能再嵌入到一个更大亏格的曲面上去。所以图的最小完全同态的亏格是不可能大于原图的的亏格的。如果说最小完全同态的亏格大于原图的亏格，那么在把最小完全同态按原同化时的相反方向再返回原图时，这时就将是一个嵌入在比原来亏格大的曲面上的图。但这是绝对不可能的，因为在同化和还原时都是在同一个曲面上进行的，其亏格是不会发生变化的；
9、根据以上的结论，任何亏格为n＝0的平面图的最小完全同态的亏格也一定仍然是等于0的，也即任何平面图的最小完全同态一定都是平面图。要证明四色猜测，就相当于证明平面图中的完全图着色时，色数不大于4 也就可以了；
10、任何图中都有一个最大团，把最大团的顶点数叫做图的密度。由于最大团中的顶点均是相邻的，不可能再进行同化，所以图的色数一定是不小于图的密度的。由于有5—圈（密度是2）同化的结果是K3图和5—轮（密度是3）同化的结果是K4，出现了最小完全同态的顶点数比原图中最大团的顶点数大的情况，所以图的色数一定是大于等于图的密度的；
11、只所以有最小完全同态的顶点数大于最大团的顶点数的情况，是因为有顶点同化不到最大团中去。只所以有这样的不可同化顶点，又是因为有不可同化道路，该道路无论怎样同化，总是有一个顶点同化不到最大团中去的。如5—圈中的任何一个K2团以外的顶点，5—轮中的任何一个K3团以外的顶点，都对该K2团和K3团构成了一条不可同化道路；
12、从上面所说的5—圈和5—轮的结构上看，不可同化道路中的任何一个顶点都与最大团中的ω－2个顶点相邻，另外该道路的两个端点顶点又与最大团中剩下的两个顶点之一相邻，这就产生了该道路中总有一个顶点同化不到最大团中去的情况，使得图的最小完全同态的顶点数有大于最大团的可能；
13、对于某个最大团来说，有一条不可同化道路，就有一个顶点同化不到最大团中去，但当若干条不可同化道路未构形联时，均可把各道路中不相邻的顶点作为不可同化顶点，然后还可以再把这些不可同化顶点同化在一起。所以没有构成联的不可同化道路再多，也只能相当于只有一条的情况，只可能有一个顶点同化不到最大团中去；
14、如果对于某一个最大团有S条不可同化道路，且其间均已构成了联，这时由于联中任何一条道路中的各个顶点均与其他道路中的各个顶点均相邻，S个不可同化顶点不可能再同化成一个顶点，所以就有S个顶点同化不到最大团中去；
15、由于不可同化道路所构成的联只是图中的一个分子图，当然联本身的密度也一定不会大于图的密度。因为联的密度是2S，即是由每条不可同化道路各提供两个顶点所构成的团的顶点数。这个2S一定是不能大于图的密度的，这就使得构成联的不可同化道路的条数S受到一定的约束。所以又有2S≤ω和S≤ω/2的关系，也有最小完全同态的顶点数最大只可能是ω＋S＝α≤ω＋ω/2≤1.5ω，也有ω≤α≤1.5ω和ω≤γ≤1.5ω的关系；
16、亏格为n的图的最小完全同态的亏格是小于等于原图的亏格的，而原图所嵌入的曲面也有可以嵌入其上的最大完全图，这个最大完全图的顶点数也对可嵌入该曲面上的图的最小完全同态的顶点数是有所限制的。若令这个最大完全图的顶点数为V,则可嵌入该曲面上的图的最小完全同态的顶点数最大也只能是V，即有图的密度加不可同化道路的条数，是不会大于这个最大完全图的顶点数V的，即ω＋S≤V,有S≤V－ω的关系。可见任何图中不可同化道路的条数是受着双重制约的，即S≤ω/2且S≤V－ω，即S既要不大于ω/2，又要不大于V－ω；
17、虽然米歇尔斯基操作（简称M—操作）的结果得出了“存在无三角形而色数是任意大的图”的结论，但这并不影响对四色猜测的证明。因为除了K1图（独立顶点），K2图（P2道路），K3图（C3圈），P3道路，在进行了一次M—操作后的图是平面图外，其他平面图进行了一次M—操作后的图均是非平面图，均不再是四色问题所研究的对象了。以上几个平面图在进行了第二次M—操作后，也都成为了非平面图，也不是四色问题研究的对象了。这些图中最大的团是K3团，即就是进行了一次M—操作，其色数也只能比其密度增大1，而变成4，但仍没有大于4。所以说M—操作是不会影响四色猜测证明的。
雷明
二○一五年五月二十五日于长安

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

,,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，