四色定理证明

今天想到了一个证明四色定理方法，不知道是否正确，求鉴定。
（pdf版：http://download.csdn.net/detail/luuillu/3784517）


引理1： 对于可平面的简单图G=(n, m)，m<=3n-6，m是图的边数n是图的顶点数。
证明：参见图论。

引理2.设图G的度数为d，则d=2m<=6n-12<6n。 因此可平面的简单图中必有度数小于等于5的顶点。
证明： 反证法即可证明。

引理3.若向平面图G中添加若干条边后可用四种颜色着色，那么原图也可以用四种颜色着色。 此命题显然成立，直接把添加的边删去即可。

四色定理：对可平面的简单图G=(n, m)的各个顶点进行着色，最少只需要四种颜色，即可使图中相邻顶点的颜色不同。

证明：
1。当n<=4时，定理显然成立。
2.假设n<=k时定理成立，即对于不超过k个定点的平面图，用四种颜色可以完成着色，下面证明当n=k+1时，命题成立：

由引理2可知,G中必然存在度数小于等于5的顶点，找到这样的顶点A，设顶点A的度数为d(A),1<=d(A)<=5.
（1）若d(A)<=3,则先将图G中的顶点A去掉，的到图G', G'有K个顶点，由归纳假设得G'可以用四种颜色完成着色，然后在把顶点A添加到G'中，恢复出图G，接着对A进行着色，由于d(A)<=3,因此可以直接对A进行着色。
(2)
若d(A)=4,则G中有四个顶点与A相邻，设这四个顶点为B，C，D，E。由于五个顶点的完全图不是平面图，因此B，C，D，E中至少有两个点是不相邻的，假设CE不相邻，如图1所示（若实际情况与图一不同则可以向G中添加若干条边转化成图1）
 
  图1 G
先将图G中的顶点A去掉，然后添加新边CE得到图2
 

图2
将图2中的CE边收缩，使CE合并为一点。得到G ' ,如图三
 
 
图3 G'
G'中所含有的顶点数为K-1，由归纳假设可知，G'可以用四种颜色完成涂色。涂色完毕后将G’还原成图2，然后去掉CE边，接着把点A添加到图中可以得到G，此时，与A相邻的顶点只涂了三种颜色，只要给A涂第四种颜色即可。

（3）若d(A)=5.则A与5个顶点相邻，如图4所示（若实际情况与图4不同则可以向G中添加若干条边转化成图4）。
 

图4 G
为了给G着色，首先将顶点A去掉，然后添加新边BE，如图五所示： 
 

图5
然后将BE收缩为一点，得到图六：
 

图6
然后连接DF，接着将DF收缩为一点，可得到图七,即G'：
 
 
图七
此时G'中包含k-2个顶点，由归纳假设可知，G’可以用四种颜色完成着色，着色完毕后可以按以上相反的顺序恢复出原图G，此时在图G中，与A相邻的五个顶点只用了三种颜色，因此只需给A涂第四种颜色即可完成着色。
证明完毕。

大牛！ 能否设计一个算法和程序来对任意图进行四着色？

我发现错误了，结贴。