计算机科学论坛--关于四色猜想的证明

贴子主题：关于四色猜想的证明

本主题类别:

关于四色猜想的证明
1、证明任何平面均为四可着色，即证明极大平面图是四可着色的。
极大平面图可以通过一个非极大平面的平面图加边得到
而平面图也可以通过某一极大平面图去边得到（注  同一阶的极大平面图存在异构）
2、 G为n(n>=3)阶简单平面图的简单连通图，G为极大平面图当且仅当G的每一个面的次数均为3.
证明：必要性
因为G为简单平面图，所以G中无环和平行边，又因为G是至少有3个顶点的极大平面图，所以G连通且无割点和桥，于是G中各面的边界数均为圈且次数均大于3.下面只需证明各面的次数均不大于3。否则没存在面Ri,deg(Ri)=S>=4见图1。在G（平面嵌入）中，若V1,V3不相邻在Ri内加边（V1,V3）不破坏平面性，这矛盾于G为极大平面图，因而（V1,V3）必相邻；类似的，（V2,V4）必相邻且边(V2,V4)也在Ri的外部，边（V1,V3）于（V2,V4）均在Ri的外面，无论用怎样的画法，它们必相交，这又矛盾于G是平面图，所以S=3
充分性
若G中不存在不相邻等点，结论显然。若G中存在不相邻顶点，只需证明任何不相邻顶点之间再加边均会产生边之间的相交即可。没U,V为二不相邻的顶点，则U,V不可能都在外部面R0的边界上。因而至少有一个顶点，比如V不在R0的边界上，见图2，则与V关联各边也不在C0上，没G’=G-V，G’中存在原来含V的圈C，因为U和V不相交，所以U不在C上，由约当定理可知，若加边（U,V），则它必与C相交，所以G为极大平面图。
3、当n=3时  极大平面图是三个点，由于只有3个顶点，故是四可着色的
当n=4时  可以在三个点的极大平面图加一个点得到四个点极大平面图，而该点只能加在三个点的极大平面图的面中或加在边上，而该点最多与三个点连接，故四个点的极大平面图。
假设k个顶点的极大平面图是是四可着色的。
在该极大平面图加一个点可以得到k+1个顶点的极大平面图。
而这个点只能加在这个极大平面图的面上或边上：
1. 该点加在面中，则该点最多与三个顶点相连之后得到极大平面图，而这三点只用了三种颜色，故可以用第四种颜色染上。
2. 该点加在边上，则由于在边上加了一个点，故将该边收缩，就得到k-1个顶点的图，将其中的平行边删除得到平面图，而k-1顶点的平面图是四可着色的，故可以将加点的边染成相同颜色，那么与新加的点可以相连组成极大平面图的点最多用了三种颜色。
综上有k+1顶点的极大平面图是四可着色的。
故所有的平面图是四可着色的。


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	78.125ms