极大图的4—着色方法

雷明85639720

极大图的4—着色方法
雷  明
（二○一五年四月二十八日）

极大图是平面图中顶点相邻关系最复杂的一种，如果能证明极大图的色数是不大于4 的，那么对极大图通过去边或去点而得到的任意平面图的色数也一定是不会大于4 的，因为这样做的结果只会使图的色数减少而不会增加。
顶点数最少的极大图是3—圈，也即K3图，在其任何一个面中增加一个顶点，则最多只可能与三个顶点相邻，给其着上与其三个相邻顶点所不同的第四种颜色即可，该图变成一个K4图，但仍是一个极大图；在这个极大图中的任何一个面内增加一个顶点，该顶点仍可着已用过的四种颜色之一，得到的图仍是极大图；若在极大图的任何一条边上增加一个顶点时，这个顶点最多也只能与四个顶点相邻，是一个4—度顶点。根据坎泊的证明，这种4—度的待着色顶点一定是可以着上图中已用过的四种颜色之一的。就这样一步步的增下去，得到的图都是极大图，图中也绝不会出现第五种颜色，所以说任何极大图都是4—可着色的。
极大图是4—可着色的，把极大图经去边或去点而得到的任何平面图的色数只全减少而不会再增加，所以，任意平面图的色数也是不会大于4 的。这也就证明了四色猜测是正确的。
雷  明
二○一五年四月二十八日于长安

雷明85639720

,,,,,,,,