[原创]着色法证明四色猜测的又一种简单方法

雷明85639720

[watermark]
以上的DOC格式文件，打不开，我只好用普通格式发送了，但图发不上去，文字也小点，请读者包涵。我也请别的注册用户把上面的文件打开一下试试，如果能打开，请告诉我打开的方法，我在这里提前感谢了。雷明，2010，2，23。

着色法证明四色猜测的又一种简单方法
             雷  明
   （二○○九年十一月二十五日）
    这一方法与坎泊的方法正好相反。坎泊的方法是基于地图中总存在着相邻区划数小于等于5的区划和不面图中总存在着顶点度小于等于5的这一特征，证明了图的顶点数大于等于5时，在某顶点周围的所有顶点都着上四种颜色后，通过坎泊交换，可以给该顶点着上已用过的四种颜色之一；而这里要讲到的又一简单的着色法，则是基于地图是一个3—正则图，其对偶图则是一个极大图这一特征，在其顶点数大于等于4时，给其任何一个面中增加一个顶点，这一顶点只与3个顶点相邻，只用去了3种颜色，该顶点一定可以着上已用过的四种颜色之一。
   
    地图是一个平面图，平面图的对偶图仍是平面图。给地图中面的着色就相当于给其对偶图的顶点着色。地图是一个3—度正则的平面图，即图中各顶点均连有3条边，其对偶图一定是一个极大图，即图中所有的面均是3—边形，即3—圈。极大图的边数在相同顶点数的图中是最多的，即极大图中顶点之间的相邻关系在平面图中也是最复杂的。一个极大图如果能够4—着色，那么非极大图和地图也就一定能够4—着色。所以我们在证明四色猜测时只要证明极大图能够4—着色就行了。现采用数学归纳法证明如下：
    1、当图中顶点数v＝1时，是一个K1图，用一种颜色就可以了，色数γ＝1，如图1中的红；
    2、当图中顶点数v＝2时，是一个K2图，用两种颜色也就可以了，色数γ＝2，如图2中的红与兰；

    3、当图中顶点数v＝3时，是一个K3图，这时图已具有了极大图的性质，图中的两个面（Ⅰ和Ⅱ）均是3—边形面，这时用三种颜色也就可以了，色数γ＝3，如图3中的红、兰和绿；

    由于极大图的面均是3—边形面，所以无论在那个面中增加一个顶点，最多也只增加3条边，该顶点最多只能与3个顶点相邻，即该顶点周围的顶点最多只能用3种颜色，这时该顶点只能着上与其周围的3个顶点都不相同的颜色就完全可以满足着色的要求。所以
   
    4、当在顶点数v＝3的K3图中的任一个面中增加一个顶点即v＝4时，图就成了一个K4图，增加的这个顶点就只能用第四种颜色，则色数γ＝4，如图4中的红、兰、绿和综；
现在图中已经用了四种颜色，它们分别是红（•）、兰（•）、绿（•）和褐（•）四种颜色。
    5、当在v＝4的基础上，在某个面中再增加一个顶点时，其周围也只有三个顶点，也只能增加3条边，否则图中就会出现交叉边，就会成为非平面图。与其相邻的三个顶点只能占用三种颜色，还有一种颜色可供该点着上，其色数γ还是4，如图5中的顶点5仍可用红色，顶点6仍可用褐色；
    6、往后一次次的增加顶点数，所增加的顶点总能着上前面已用过的四种颜色之一，所以说当v＝n时，γ＝4，这说明了有n个顶点的极大图是可以4—着色的，如图6中的顶点n仍可用绿色；
    7、当v＝n＋1时，顶点虽增加了1，但这个顶点仍可使用已用过的四种颜色之一，即其色数γ还是4，如图7中的顶点n＋1仍可用褐色。
    到此，就证明了极大图的四色猜测是正确的。如果从这个已经4—着色的极大图中去掉若干条边，则图就变成了一个非极大的平面图，这时图中仍只是用了4种颜色，所以说，只要证明了极大图能够4—着色，那么与其同顶点数的非极大图也一定是能够4—着色的。到此也就证明了任意平面图和地图的四色猜测是正确的。即任何平面图或地图着色时，四种颜色一定够用了。
              雷  明
  二○○九年十一月二十五日于长安