看完留下你的高论?
预备知识:
定理(一):给定无向图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|
代入欧拉公式得
|V|-|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
|