四色猜想的证明

子登

看完留下你的高论？
预备知识：
定理（一）：给定无向图G=<V,E>，则 =2|E|。
证明：由于图G中每一条边都是联结两个结点，故每条边对于结点的度数之和都贡献为2。于是，图中所有结点的度数之和必为偶数，且等于图中边数的2倍，即 =2|E|。
欧拉公式：设G=<V,E,F>是连通平面图，则|V|-|E|+|F|=2。
证明略。
推论1：给定连通简单平面图G=<V,E,F>。若|V|>=3,则|E|<=3|V|-6。
证明：因为G是|V|>=3的简单平面图，则它的每个平面至少有三条边组成。所以，G中各个面的边的总数大于或等于3|F|，又由于一条边至多为两个面的边界，因此G中的各个面的边的总数小于或等于2|E|，故
                  2|E|>=3|F|
即                 |F|<=2/3|E|
代入欧拉公式得
|Ｖ｜－｜E｜+2/3|E|>=2
化简|E|<=3|V|-6
推论2：设G=<V,E>是一个连通简单平面图，若|V|>=3,则存在v属于V，使得d(v)<=5(d(v)表示以v为结点边的个数)。
证明：假设G中每个结点v，都有d(v)>=6，则由定理（一）及|V|>=3可得
     6|V|<=∑d(v)=2|E|
即有|E|>=3|V|>3|V|-6，与推论1矛盾。
证明的开始：
对于平面图G=<V,E>（V为结点，E为边）着色时，需要的最少颜色数称为G的着色数，记为X(G)。
四色猜想可归结为如下定理：
（四色定理）对于任何简单平面图G=<V,E>，均有X(G)<=4。
证明如下：
显然只需考虑连通简单平面图G的情形即可。对|V|(表示结点数)归纳证明。
当|V|<=4，显然X(G)<=4。
现在考虑图G1=<V1,E>,|V1|=k+1的情形。由推论2可知，存在v0 V1,使得d(v0)<=5.在图G1中删去v0,得图G1-v0。由归纳假设，X(G-v0)<=4。
现在研究G1中结点v0的着色。只需考虑三个方面：
第一：若d(v0)<4，则与v0邻接结点数不超过4，故可对v0着色，得到一个最多是4色的图G1。
第二：若d(v0)=4，设与v0邻接结点依顺时针排列为v1，v2，v3和v4。它们分别着色为c1，c2，c3和c4，如图（1）所示。

考虑由结点集合Vc1,c2={v|v V(G1-v0)  (v)=c1或c3}所诱导的G1-v0的子图〈Vc1,c3〉。若v1，v3属于〈Vc1,c3〉的不同分图，则在v1所在的分图中，调换c1与c3后，得到G1-v0的五着色 1。因为此时 1(v1)=c3,  1(vi)=ci,  i=2,3,4.故令 1(v0)=c1,得到G1的一种四着色。
若v1，v3属于〈Vc1,c3〉的同一分图中，则由结点集Vc1,c3  {v0}的G1的诱导子图< Vc1,c2  {v0}>中含有一个圈C,而v2 与v4不能同时在该圈的内部或外部，即v2 与v4不是邻接点（如图1）。于是考虑由结点集Vc2,c4 ={v|v V(G1-v0)   (v)=c2或c4}所诱导子图< Vc2,c4>, v2 与v4必属于< Vc2,c4>的不同分图，做上面类似调整，又可得到G1的一种四着色。
第三:若d(v0)=5，设与v0邻接结点依顺时针排列为v1，v2，v3，v4和v5。由归纳假设G1-v0可用4种颜色着色，v1，v2，v3，v4和v5中必有两个结点的颜色相同。不妨设有两个结点的颜色为c1。则它们只存在两种结构，如图（2）和

图（3）所示。  
考虑图（2）：
考虑由结点集合Vc2,c4 ={v|v V(G1-v0)   (v)=c2或c4}所诱导的G1-v0的子图。该情形与d(v0)=4时相似，显然存在G1的一种四着色。
考虑图（3）
考虑由结点集合Vc2,c4 ={v|v V(G1-v0)   (v)=c2或c4}所诱导的G1-v0的子图。若v2,v5属于<Vc2,c4>的不同分图，则在v2所在的分图中调换c2,c4的颜色后，得到G1-v0的四着色 1。因为此时 1(v2)=c4, 1(v1)=c1, 1(v3)=c3,  1(v4)=c1.  1(v5)=c4.故令 1(v0)=c2,得到G1的一种四着色。
若v2,v5属于<Vc2,c4>的同一分图中。则考虑由结点集合Vc3,c4 ={v|v V(G1-v0)   (v)=c3或c4}所诱导的G1-v0的子图。若v3,v5属于<Vc3,c4>的不同分图，则同上存在G1的一种四着色。
若v2,v5属于<Vc2,c4>的同一分图，v3,v5也属于<Vc3,c4>的同一分图，则由结点集合Vc2,c4  {v0}的G1的诱导子图<Vc2,c4  {v0}>中含有一个M圈。由结点集合Vc3,c4  {v0}的G1的诱导子图<Vc3,c4  {v0}>中含有一个N圈。如图（4）。
由图知，显然v1，v3不能同时在M圈的内部或外部；
V2，v4不能同时在N圈的内部或外部。
在v1所在的分图中调换颜色c1,c3；
在v4所在的分图中调换颜色c1,c2。得
1(v1)=c3,  1(v2)=c2,  1(v3)=c3,  1(v4)=c2,  1(v5)=c4故令 1(v0)=c1，即得G1的一种四着色。
综上，故X(G1)<=4。由归纳原理，定理得证。
参考文献：
【1】李盘林 李丽双 李洋 王春立 《离散数学》高等教育出版社     2002

子登

请大家发表意见

雷明85639720

子登先生,请把你的图传上来,你可以在上传时使用浏览器,然后上传.雷明

luckylucky

呵呵。这个证明思路可以说开头不错。不过后面会有大石头。这个证明和我10年前的证明可以说是完全一样。后来请了一个数学系的教授给予批评。他很快给出了个难以有效证明的反例。如下
即当新着色点周遍存在5个顶点。我们按顺时针方向分别已经被着色为 c1,c2,c3,c4,c2。其对应的顶点不失一般性的定义为v1,v2,v3,v4,v5。那么此时如果从v1到v3存在一条链，其已经且仅被着色为c1,c3的双色。从v1到v4存在一条链，其已经且仅被着色为c1,c4。其上述这两条链存在交叉（显然交叉点的着色是c1)，且交叉点不为v1。此时你很难用简单方式来证明。我曾经尝试过反例法证明。发现任何我能列出的证明方式，均存在反例使得不可完整说明问题。而同时这些反例又可以通过扩大证明内容被证明。
关于你的证明，只能遗憾的说，你没有完整证明。