四色猜测证明方法集锦

雷明85639720

四色猜测证明方法集锦
雷  明
（二○一五年四月二十九日）

一、前    言
我历来是主张“不画图，不着色证明四色猜测”的，但这也是从“画图——着色”的经验教训中得到的收获。因为图有无穷多个，是永远也画不完，着不完的。走这条路等于是永远也不可能把四色猜测证完的。用数学归纳法好象也是无济于事的，因为图中的顶点排列是没有任何规律的。
不画图，不着色证明四色猜测的观点主要是依赖于图同化的最后结果一定是一个顶点数最少的完全图（即最小完全同态），该完全图的顶点数就是原图的着色数。因为最小完全同态的每一个顶点都是由若干个互不相邻的顶点同化而来的，而这若干个顶点着色时是可以使用同一颜色的。
现在我把我总结出来的“不画图，不着色证明四色猜测”的十多种方法的短文汇集在一起，编成《四色猜测证明方法集锦》一文。希望与网友们交换，请大家多提意见。
二、“不画图，不着色证明四色猜测”的要点
    1、把图中不相邻的顶点凝结到一起的过程叫同化，可同化在一起的顶点是可以着同一颜色的：
2、任何图同化的最后结果一定是一个顶点数不能再少的完全图，这就叫原图的最小完全同态，该完全同态的顶点数就是原图的色数；
3、任何图的最小完全同态的亏格都是小于等于原图的亏格的，所以亏格为0的平面图的最小完全同态的亏格也一定是0，即平面图的最小完全同态的也一定是一个平面图；
4、图的最小完全同态就是一个完全图，在平面图中只有K1，K2，K3和K4四个完全图，其色数分别是1，2，3，4，都是小于等于4的；
5、这就证明了四色猜测是正确的。
三、赫渥特公式的推导
设一个亏格为n的图同化后所得到的最小完全同态是Kv，该同态是一个顶点数是v的完全图。该Kv一定是能够满足多阶曲面上图的欧拉公式v＋f－e＝2（1－n）的,因为任意图中都有3f≤2e，把f≤2e/3以上的欧拉公式中得
     3v－e＝≥6－6n
这就是多阶曲面上的图中的边与顶点的关系。再把完全图中边与顶点的关系e＝v（v－1）/2代入上式得
        v2－7v＋12（1－n）≤0
解这个关于完全图（即亏格为n的图的最小完全同态）的顶点数v的一元二次不等式，得正根是
v≤（7＋√（1＋48n））/2
因为完全图的色数就等于其顶点数，所以又有
γ≤（7＋√（1＋48n））/2
这就是赫渥特的地图着色公式。当n＝0时，上式的计算结果是γ≤4，这就是四色猜测。四色猜测得证是正确的。
四、图的最小完全同态的亏格
任何图通过同化最后都可以得到一个顶点数最少的最小完全同态，该同态的顶点数就是原图的色数。现在要问这个同态的亏格与原图的亏格是什么关系。
图的亏格是其可嵌入的曲面的最小亏格，那么亏格是n的图一定是嵌入在亏格为n的曲面上的图。该图的同化是在亏格为n的曲面上进行的，最后得到的最小完全同态也一定是嵌入在亏格是n的曲面上的图。我们知道K5的亏格是1，其最小完全同态就是原图K5本身，其亏格也应是1；而K3,3的亏格也是1，但其最小完全同态却是K2，亏格却是0；这就说明图的最小完全同态的亏格一定是小于等于原图的亏格的。但图的最小完全同态的亏格有没有大于原图的亏格的情况呢。我们用反证法进行证明。
假设一个任意图的最小完全同态的亏格是大于原图的亏格的，即n同态＞n原图，那么该完全同态可嵌入的曲面的最小亏格应为n同态曲面＝n同态，而原图可嵌入曲面的最小亏格应是n原图曲面＝n原图。由于n同态＞n原图，似乎也应有n同态曲面＞n原图曲面，但这是不可能的。按理把最小完全同态按原同化时的反方向展开后，就可得到同化前的原图。但这里所得到的“原图”可嵌入的曲面的最小亏格却变成了n同态贡面，而大于n原图曲面，导致出现了把最小完全同态按原同化时的反方向展开后的图的亏格与原图亏格不相同的矛盾，即n“原图”≠n原图。说明原假设的任意图的最小完全同态的亏格可以大于原图的亏格是错误的，必须否定。所以就有任意图的最小完全同态的亏格一定小于等于原图的亏格的结论。
根据以上的结论，任何亏格为n＝0的平面图的最小完全同态的亏格也一定仍然是等于0的，也即任何平面图的最小完全同态一定都是平面图。平面图中只有K1，K2，K3，K4四种完全图，其顶点数分别是1，2，3和4，都不大于4。由于图的色数等于其最小完全同态的顶点数，所以也有平面图的色数都是不会大于4 的结论。这就证明了四色猜测是正确的。
五、图的色数不大于图的密度的1.5倍
任何图中必有一个顶点数最多的最大团，该团的顶点数就叫该图的密度（用字母ω表示）。图同化时若在一条道路上总有一个顶点同化不到最大团中去，则该道路对于该最大团来说就是一条不可同化道路。对于同一个最大团来说，若存在相互间都有联的S条不可同化道路，则这些道路的联中的最大团的顶点数一定是2S，因为这个团只是图中的一个分子图，所以该团的顶点数最多只能与图中的最大团的顶点数相等，因此有2S≤ω，也有S≤ω/2。有S条不可同化道路，就有S个顶点同化不到最大团中去，图同化最终的最小完全同态的顶点数一定是小于等于ω＋ω/2＝1.5ω的，欺负色数也是小于等于1.5ω的。
平面图的密度只有1～4四种，这就使得一个对于图的密度来说是无穷的问题变成了一个有穷的问题。当图的密度ω＝1时，该图着色时一种颜色一定够用了。当ω＝2，图中还含有5—圈以上的寄圈时，圈中相邻的两个顶点就是一个最大团，圈中其他的顶点则构成了该最大团的一条不可同化道路，其条数是S＝1，该图着色时用ω＋S＝2＋1＝3种颜色也就够用了，不大于密度2的1.5倍3；若不含寄圈时，有两种颜色就够用了。当ω＝3，图中还含有5—轮以上的寄轮时，轮中相邻的两个轮沿顶点与轮的中心顶点也就是一个最大团，轮中其他的轮沿顶点则构成了该最大团的一条不可同化道路，S＝1，该图着色时用ω＋S＝3＋1＝4种颜色也就够用了，也没有大于密度3的1.5倍4.5；不含寄轮时，3种颜色也就够用了。当ω＝4时，似乎其色数可能有大于4 的情况，但对于图中某个最大团K4来说只要有一条不可同化道路时，图就不再是平面图了，所以说ω＝4的图着色时的色数一定是恒等于4 的。
通过以上证明，可见平面图的色数都是不会大于4的。这也就证明了四色猜测是正确的。
六、经米歇尔斯基操作的图基本上都不是四色问题研究的对象
通过对图进行米歇尔斯基（Mycielski）操作（M—操作），仅管说明“存在无三角形且色数任意大的图”，但在进行了M—操作后的图绝大多数都是非平面图，已不再是四色问题研究的对象了。
M—操作是在顶点数是v的已知基图G外增加一个顶点数是v的星形图（其顶点数是v＋1），然后再尽可能的把这个星形图的各星点与基图G的各顶点用边相连。但要保持图的密度不增加，也就是说，星形图中的任一个星点最多只能与基图G中的任一个最大团的ω－1个顶点相邻（ω是G中最大团的顶点数），这样所得到的图的色数就比基图G的色数增加1。
平面图在进行了M—操作后仍是连通平面图的，才是四色问题研究的对象。我们对以下平面图K1,K2团（P2道路）, P3道路， P4道路， K3团（C3，3—圈），C4（4—圈），K4团（W3，3—轮）分别进行一次M—操作后，K1变成了一个非连通的平面图，色数成了2，但没有大于4；P4道路，C4（4—圈）和K4团（W3，3—轮）三图都变成了一个非平面图，他们都不再是四色问题研究的对象了，当然比这三个图更复杂的图经过M—操作后也一定不再是平面图了。而只有K2团（P2道路）, P3道路和K3团（C3，3—圈）进行了M—操作后仍然是连通的平面图，其色数比原来的2，2和3都增加了1，变成3，3和4，但仍没有大于4，仍在四色问题研究的范围之内。若对这几个平面图再进行一次M—操作后，则都不再是平面图了，而成为非平面图了，也不再是四色问题研究的对象了。所以说，平面图进行一次M—操作后仍是平面图的只有K1，K2团（P2道路）, P3道路和K3团（C3，3—圈）四个图，其他的绝大多数图在进行了一次M—操作后都成了非平面图。而这四个图在进行了第二次M—操作后也变成非平面图了。他们都不再是四色问题所研究的对象了。
以上可以进行M—操作的平面图的色数虽然也都比原来增大了1，但却都没有大于4，说明了M—操作对证明四色猜测是没有影响的，四色猜测还是可以证明是正确的。
七、待着色顶点移动着色法
我们在对坎泊所创造的颜色交换技术时，已经对难着色的赫渥特图、米勒图、张氏Z图及我最近所构造的L图，用坎泊的颜色交换技术进行了4—着色，说明了任何一个5—轮构形的图都是可以4—着色的。
由于任何一个平面图中都至少存在着一个顶点的度是小于等于5 的，所以在对平面图着色时，当所遇到的待着色顶点的度是大于等于6时，就可以把该待着色顶点着上与其相邻的顶点中所用次数最少的那种颜色，而把与待着色顶点相邻那些顶点变成一个或若干个新的待着色顶点。这样一步一步走下去，就一定会找到一个或若干个度小于等于5的更新的待着色顶点，该顶点一定是可以用坎泊的颜色交换技术着上图中已用过的四种颜色之一的。就这样把一个个度大于等于6 的待着色顶点变换成度为不大于5的新的待着色顶点，给其着上已用过的四种颜色之一（这里要注意的是，同一个度不大于5 的顶点是可以多次作为新的待着色顶点的），直到把图中所有的顶点都着色完毕为至，一个图的着色就结束了。经过这样着色的平面图中是绝对不会出现第五种颜色的。这也就证明了四色猜测是正确的。
八、极大图的4—着色方法
极大图是平面图中顶点相邻关系最复杂的一种，如果能证明极大图的色数是不大于4 的，那么对极大图通过去边或去点而得到的任意平面图的色数也一定是不会大于4 的，因为这样做的结果只会使图的色数减少而不会增加。
顶点数最少的极大图是3—圈，也即K3图，在其任何一个面中增加一个顶点，则最多只可能与三个顶点相邻，给其着上与其三个相邻顶点所不同的第四种颜色即可，该图变成一个K4图，但仍是一个极大图；在这个极大图中的任何一个面内增加一个顶点，该顶点仍可着已用过的四种颜色之一，得到的图仍是极大图；若在极大图的任何一条边上增加一个顶点时，这个顶点最多也只能与四个顶点相邻，是一个4—度顶点。根据坎泊的证明，这种4—度的待着色顶点一定是可以着上图中已用过的四种颜色之一的。就这样一步步的增下去，得到的图都是极大图，图中也绝不会出现第五种颜色，所以说任何极大图都是4—可着色的。
极大图是4—可着色的，把极大图经去边或去点而得到的任何平面图的色数只全减少而不会再增加，所以，任意平面图的色数也是不会大于4 的。这也就证明了四色猜测是正确的。
九、用欧拉公式直接求平面图的色数
由于任何图的最小完全同态的亏格都是小于等于原图的亏格的，所以也有亏格为0的任何平面图的最小完全同态的亏格一定也仍然是0的结论，因此平面图的欧拉公式v＋f＝e＋2也一定也是适用于平面图的最小完全同态的。把任意图中面与边的关系3f≤2e代入平面图的欧拉公式中得
        3v－e≥6
这就是平面图中边与顶点的关系e≤3v－6。再把完全图的边与顶点的关系e＝v（v－1）/2代入其中得
        v2－7v＋12≤0
解这个关于平面图最小完全同态的顶点数v的一元二次不等式得
        v1≤4和v2≤3
其中v1≤4包含v2≤3，所以该不等式只有一个根v1≤4，即任何平面图的最小完全同态的顶点数都是小于等于4的。
     因为任何图的色数都等于其最小完全同态的顶点数，所以也有平面图的色数也是小于等于4 的结论。这就是四色猜测。四色猜测得到证明是正确的。
十、用完全图的边与顶点的关系直接求平面图的色数
亏格为0的平面图的最小完全同态仍是一个亏格为0的平面图，它的顶点数就是该平面图的色数。亏格为0 的平面图中的完全图只有K1，K2，K3和K4四种。
已知完全图的边与顶点的关系是
e＝v（v－1）/2
同时又符合任意平面图中边与顶点的关系
e≤3v－6
令以上两式相等，即有
        v2－7v＋12≤0
解这个关于平面图最小完全同态的顶点数v的一元二次不等式得
        v1≤4和v2≤3
其中v1≤4包含v2≤3，所以该不等式只有一个根v1≤4，即任何平面图的最小完全同态的顶点数都是小于等于4的，也即任何平面图的色数一定是小于等于4的。这就是四色猜测。四色猜测得到证明是正确的。
十一、逐渐还原度小于等于5的顶点给平面图的4—着色
我们在对坎泊所创造的颜色交换技术时，已经对难着色的赫渥特图、米勒图、张氏Z图及我最近所构造的L图，用坎泊的颜色交换技术进行了4—着色，说明了任何一个5—轮构形的图都是可以4—着色的。
由于平面图中一定存在着若干个度小于等于5的顶点，若把这些顶点从图中去掉时，图仍然是一个平面图，但同时又会产生新的度小于等于5的顶点。再把新生成的度小于等于5的顶点去掉，再产生新的度小于等于5的顶点。就这样一直的去掉下去，图最后将成为一个顶点数小于等于4的图，这个最后的小于等于个4个顶点的图进行4—着色是没有问题的。
现在再按去点时的相反方向往回走，先给上面已着色的4顶点图还原最后一次去掉的那个度小于等于5的顶点，图中就有5个顶点了。这时待着色的顶点（即被还原的顶点）的度也一定是小于等于5的，该顶点也是可以着上图中已用过的四种颜色之一的。再还原最后第二次去掉的那个度小于等于5的顶点，图中就有6个顶点了，这时的待着色顶点的度还是小于等于5的，也是能着上已用过的四种颜色之一的。以后所还原的顶点的度都是小于等于5的，也一定能着上已用过的四种颜色之一的。直到把所去掉的顶点全部还原完为止。这时，所有的顶点都是着上了已用过的四种颜色之一，没有出现第五种颜色。这也就证明了四色猜测是正确的。
十二、用断链的方法给待着色顶点着色
一个构形的待着色顶点，如果其围栏顶点占用的颜色数未达到4，该待着色顶点都是可以着上四种颜色之一的；如果围栏顶点已占用完了四种颜色，则必须想办法从围栏顶点中空出一种颜色来，然后给待着色顶点着上。如何空出颜色，这就得要用坎泊的颜色交换技术了。
用坎泊的颜色交换技术空出颜色的原则是：对于以待着色顶点为中心顶点的轮的对角顶点的颜色所构成的链是不连通的时，才可进行交换，也才能空出颜色。而若是连通链时，即就是交换了也是空不出颜色来的。
4—轮构形一定是可以通过交换空出颜色给待着色顶点着上的。而5—轮构形其中的两条连通链只有一个共同的起点或是只有一个交叉顶点时，也一定是可以通过交换空出颜色来的，而只有两条连通链既有共同的起点，又有一个交叉顶点时，如赫渥特图，米勒图，张氏Z—构形图和L—构形图，如论无何是不能通过交换对角链的办法空出颜色的。怎么办，就得想办法对图中已有的连通链进行“断链”，使原来连通的链变成不连通的，然后再使用坎泊的颜色交换技术空出颜色来给待着色顶点着上。而“断链”的过程仍然是施行坎泊的颜色交换技术的过程，只是这一过程的交换与5—轮的轮沿顶点是无关的。我们对赫渥特图，米勒图，张氏Z—构形图和L—构形图的着色都是用的这种办法。
断链方法的原理是：用四种颜色A、B、C、D所能构成的链有六种，即A—B、A—C，A—D，B—C，B—D和C—D六种，如果有A—B链是连通的时，则该链中的A和B在该链以外，只能与C和D相邻，构成A—C链和A—D链或者B—C链和B—D链，从A—B链上的任何一个A或B顶点开始交换上述的A—C链和A—D链或者B—C链和B—D链中的一种，都可以使A—B链上的被交换的顶点A或顶点B变成C或D，使A—B链断开。这样就可以对5—轮轮沿中的顶点A或B施行A—B链的交换，空出A或B来给待着色的5—轮中心顶点着上。
可以说任何平面图中的任何链都是可以通过这一方法“断开”的，所以也就可以说明任何平面图着色时是不会用到第五种颜色的。这也就证明了四色猜测是正确的。
十三、从地图的角度推导赫渥特的地图着色公式
设在某亏格为n的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色地图。那么这个“国数最小的”地图中也就应有γ个“国家”。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与别的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域的总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这f（f－1）条边界线中每条边界线都是计算了两次的，则这个地图中的“边界线”的总条数即边数应是e＝f（f－1）/2。又因为地图是一个3—正则图，即每一个顶点都连着3条边，即所谓的“三界点”，所以该地图的总边数也可以写成e＝3v/2，从而有3v＝2e＝f（f－1）的关系。用区域数（即面数）f来表示顶点数v和边数e，则有v＝f（f－1）/3和e＝f（f－1）/2。把v＝f（f－1）/3和e＝f（f－1）/2代入到多阶曲面上图的欧拉公式v＋f－e＝2－2n则得到
f2－7f＋12（1－n）＝0
解这个关于“国数最小的”地图的区域数f的一元二次方程得正根是
        f＝（7＋√（1＋48n））/2
因为区域数必须是整数，所以上式还得向下取整，得
        f＝＜（7＋√（1＋48n））/2＞
式中用＜＞表示其中的数字向下取整。又因为f是两两均相邻的“国数最小的”地图的“国数”，即区域数，所以这个“国数最小的”地图染色时也必须用与其区域数相同的颜色数，所以又有
        γ＝f＝＜（7＋√（1＋48n））/2＞
这就是赫渥特的地图着色公式的“等式部分”。
从以上的讨论看，这个区域数f只是某一亏格为n的曲面上“国数最小的”地图中的“国数”最大者。若从这个“国数最小的”地图中去掉一条边，或者去掉一个“三界点”顶点及其所连的3条边，该地图中的区域数就都会减少。这个“国数最小的”地图原来是一个区域染一种颜色，那么现在区域数少了，所用的颜色数也就会减少下来。所以上式还可以再增加“不等式部分”，即
        γ＝f≤＜（7＋√（1＋48n））/2＞
这就是赫渥特地图着色公式的全貌了，其中既有等式又有不等式。
式中当曲面的亏格为n＝0时，其色数γ＝f≤4，这就是地图四色猜测。这也就证明了四色猜测是正确的。
十四、用欧拉公式直接求地图的染色数
设在某亏格为n的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色地图。那么这个“国数最小的”地图中也就应有γ个“国家”。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与别的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域的总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这f（f－1）条边界线中每条边界线都是计算了两次的，则这个地图中的“边界线”的总条数即边数应是e＝f（f－1）/2。又因为地图是一个3—正则图，即每一个顶点都连着3条边，即所谓的“三界点”，所以该地图的总边数也可以写成e＝3v/2，从而有3v＝2e＝f（f－1）的关系。用区域数（即面数）f来表示顶点数v和边数e，则有v＝f（f－1）/3和e＝f（f－1）/2。
如果直接把v＝f（f－1）/3和e＝f（f－1）/2代入到亏格为n＝0的平面图的欧拉公式v＋f－e＝2中，就可以得到
f2－7f＋12＝0
解这个关于f的一元二次方程得两正根分别是
        f＝4和f＝3
取大值f＝4。这里也只有等式部分。因为两两均相邻的4 个区堿染色时必须用四种颜色，所以也有γ＝f＝4。
这里的f＝4就是平面或球面上色数小于等于4的两两均相邻的“国数最小的”地图中的“国数”最大者，这个地图染色时必须用与其区域数相同数目的颜色。若从这个“国数最小的”地图中去掉一条边，或者去掉一个“三界点”顶点及其所连的3条边，该地图中的区域数就都会减少。这个“国数最小的”地图原来是一个区域染一种颜色，那么现在区域数少了，所用的颜色数也就会减少下来。所以上式还可以再增加“不等式部分”，即
    γ＝f≤4
这就是地图四色猜测。这也就证明了地图四色猜测是正确的。
十五、用哈德维格尔猜想证明四色猜测
根据哈德维格尔猜想（1943年，后已被证明是正确的），“若图G是n色的，则G可以收缩为一个完全图Kn。”这里的“收缩”一词与我所用的“同化”一词是同一个概念，都是把两个不相邻的顶点凝结在一起的过程。我们通过同化理论也可以得到任何图同化的最后结果一定是一个顶点数最少的完全图，该完全图的顶点数就是原图的色数，这个完全图就叫原图的最小完全同态。
一个图只要其中含有K5团作其分子图，该图一定不是平面图，那么这样的图同化的最后结果一定是一个顶点数大于等于5的完全图；反过来，不含K5团作其分子图的图，却不一定都是平面图。但可以肯定，平面图中是一定不含K5团作其分子图的。虽然不含K5团作其分子图的图同化时不一定都会得到顶点数小于5的完全图，但至少可以肯定不含K5团作其分子图的平面图在同化时，是可以得到顶点数不大于4的完全图。这些完全图也是平面图。这也就是我们通过同化理论得出的“任何图同化后的最小完全同态的亏格一定是小于等于原图的亏格的；相应的也就有亏格为0 的平面图同化后的最小完全同态的亏格仍是0的结论”。
既然平面图同化的最终结果不会得到顶点数大于等于5的完全图，那么平面图同化的最终结果只能是顶点数小于等于4的完全图了，这样的完全图在着色时，最多4种颜色也就够用了。这也就证明了四色猜测是正确的。
十六、各密度的平面图的最小完全同态不同
——四色猜测的又一种证明方法
（二○一五年五月十一日补充）
1、任何图都有一个顶点数最小的完全同态，且其亏格绝不会大于原图的亏格。这就是说平面图的最小完全同态的亏格一定仍然是0，也即平面图的完全同态也一定是平面图。完全同态也是一个完全图，而是平面图的完全图只有K1，K2，K3，K4四种，其色数分别是1，2，3，4，均不大于4。
2、通过对图的同化运算的研究，知道图的最小完全同态的顶点数不会小于图的密度，也不会大于图的密度的一倍半。图的最小完全同态顶点数比其密度的增大，主要是因为图中有不可同化道路所引起的，因为该道路中总有一个顶点是同化不到最大团中去的。比如一个5—轮，其最大团是K3，5—轮同化的最后结果总是一个顶点数比K3顶点数多1 的K4。这是因为轮沿顶点数大于等5 的奇轮中的每一个K3团外的其他顶点，对于该K3团来说就是一条不可同化道路，其中一定有一个顶点不可能同化到该K3团中去。
3、对于一个最大团来说，若有多条不可同化道路，且它们之间又构成了联时，就有与不可同化道路条数相同数目的顶点同化不到最大团中去。但这个不可同化道路的条数是受一定约束的。即受联中的最大团的顶点数不能大于图本身最大团的顶点数的约束。该联中的最大团的顶点数是构成它的不可同化道路条数的2倍，所以不可同化道路的最大条数是不能大于图的密度的一半的。用S表示不可同化道路的条数，用ω表示图的密度，则有S≤ω/2。
4、一个平面图的最小完全同态的顶点数无论是多少，但它一定是不能大于4 的，因为这个完全同态也是一个平面图，如果其顶点数大于4，则该完全同态就成为一个非平面图了。最小完全同态的顶点数是由图的密度与构成联的不可同化道路的条数之和构成的，所以也有ω＋S≤4，即S≤4－ω的结论。
5、可以看出满足S≤ω/2和S≤4－ω二者中S的较小值即是各密度条件下的平面图中最大可能的不可同化道路的条数。可以看出，当图的密度ω＝1和4 时，不可同化道路的条数S＝0，即不可能有不可同化道路；当ω＝2和3时，S≤1，即最大可能的不可同化道路只有一条。
6、因为图的色数就等于其最小完全同态的顶点数，所以，密度为1 的平面图K1的色数为1；密度为2的平面图的色数最大为3；密度为3的平面图的色数最大为4；密度为4的平面图的色数最大仍为4；都没有大于4。这也就证明了四色猜测是正确的。
十七、编    后
四色猜测是可以用手工证明的，且证明的方法是有多种的。所谓电子计算机证明了猜测的说法是错误的。它只能说是用大量的图对四色猜测的一个验证而已。它对那2000多个图的着色与我们人用手工对别个的几个图的着色并没有什么原则上的区别，只能说明对已经着过色的图来说，四色猜测是正确的，但并没有得出对于任意平面图来说，四色猜测是否正确的结论。所以说，用“画图——着色”的方法是永远也不可能对猜测进行证明的。


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

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










   

                 

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，