四色问题讲座：第四讲 把无穷问题转化成有穷问题

雷明85639720

四色问题讲座：第四讲  把无穷问题转化成有穷问题
    雷  明
平面图有无穷多个，极大平面图也有无穷多个，每个极大平面图中的顶点数也可以是无穷多的，图中每个顶点的度也可以是无穷大的。这就决定了极大平面图着色时所研究的对象——构形——也一定是无穷多的。既是无穷多的，当然也就是永远也研究不完的。但图论中却可以给出证明，证明任何平面图中至少都含有一个顶点的度是小于等于5的顶点。也就是说，各顶点的度全部都是大于等于6的平面图是不存在的。这就为着色时一定能够把最后的待着色顶点放在度是小于等于5的顶点之上创造了条件。度是小于等于5的顶点就成了平面图中不可避免的顶点，待着色顶点的度是小于等于5的构形也就成了平面图中的不可避免构形。这就把一个无穷的问题转化成了有穷的问题。以后就只需要研究度是小于等于5的不可避免构形的可约性就可以了。在各种情况下的有限个不可避免构形都是可约的了，四色问题也就解决了。
极大平面图中至少有一个顶点的度是小于等于5的证明如下：
因为极大平面图的边是相同顶点数的平面图中最多的，其边与顶点的关系一定满足e（边）＝3v（顶点）－6，所以各顶点的度的总和则应是∑d＝2e＝2（3v－6）＝6v－12，各顶点的平均度为d平均＝2e/v＝（6v－12）/v＝6－12/v。当v趋于无穷大时，平均度的极限值是6，但永远也不会等于6。对于一个具体的图来说，其顶点数一定都是有限的，不可能是无穷多的，其平均度也一定是小于6的。这就证明了任何平面图中一定至少有一个顶点的度是小于等于5的。

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，