数学归纳法证明四色猜测——四色猜测证明方法之九

雷明85639720

数学归纳法证明四色猜测
——四色猜测证明方法之九
雷  明
（二○一六年十一月三日）

用v表示图的顶点数，用e是图的边数，用f是图的面数，用γ表示图的色数。
当v＝1时，一种颜色就够用了，γ＝1＜4；
当v＝2时，两种颜色也就够用了，γ＝2＜4；
当v＝3时，边数最多时是K3图，是一个极大图，也是一个完全图，两两顶点均相邻，必须用三种颜色着色，γ＝3＜4；

当v＝4时，新增加的这第4个顶点，只有位于上面的K3图的一个面内时，最多可以增加3条边，使K3成为一个极大图K4（如图1左图），也是一个完全图，两两顶点也均相邻，着色时四种颜色也就够用了，γ＝4≯4；
当v＝5时，新增加的顶点，可以在图中的一个面内，也可以在图的一条边上（如图1），只要图不变成非平面图的情况下，尽可能多的使该顶点与图中的其他顶点相邻，最后都可以成为一个极大图：
若该顶点处在图的一个面中（如图1的左图）时，它只能与三个顶点相邻，它还有除三个顶点所着颜色以外的第四种颜色可着；
若该顶点处在图的一条边上（如图1的右图）时，它也只能与四个顶点相邻，按照坎泊1879的证明，这个顶点一定是能着上四种颜色之一的。这就证明了v＝5时的极大图也是可4—着色的，其色数γ＝4≯4。
    从图1中还可以看出，不管增加的点是增加在何处，图中都是因增加了1个顶点而增加了3条边和两个面。若再在图中增加顶点，只要图不变成非平面图，所得到的图一定是极大图，就一定都是可4—着色的，色数都是γ＝4≯4；
当然v＝k时的极大图，当然也是可4—着色的，色数仍是γ＝4≯4。
已知在极大图中都有e＝3v－6和f＝2v－4的关系，所以这里也应有e＝3k－6和f＝2k－4的关系；当v＝k＋1时，按上面的证明和分折，所增加的这一个顶点不但是可以着上图中已用过的四种颜色之一的，而且图中也因增加了这一个顶点而增加了三条边和两个面，使得图的边数和面数分别变成了e＋3和f＋2。代入上两式得：e＋3＝3（k＋1）－6和f＋2＝2（k＋1）－4，化简后仍有e＝3k－6和f＝2k－4的关系，图仍是一个极大的平面图。
到此就证明了任何极大图都是可4—着色的。因为在相同顶点数的平面图中，极大图的边数是最多的，所以边数比极大图少的任意平面图的色数也一定是不会大于4的。这也就证明了四色猜测是正确的。

雷  明
二○一六年十一月三日于长安

注：此文已于二○一六年十一月三日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

谢谢了。

雷明85639720

，，，，

雷明85639720

什么乱七八糟的！