定理751设G’是G的对偶图,则z(G)=x(G)。 证明:由定义立即可知 四色猜想:任何地图只需用4种颜色来染色,就可使得任何具有公共边界的两 个区域染不同的颜色。 四色猜想的图论表述:对任何平面图的平面嵌入G,x'(G)≤4。 二、四色猜想的几种等价表述 定理752对任何平面图G,z(G)≤4当且仅当其色多项式P(G,4)>0 证明:由色数和色多项式的定义立即可知。 定理753下列三个命题等价: (1)每个平面图都是点4可染的; (2)每个平面图的平面嵌入是面4可染的; (3)每个简单2边连通3正则平面图是边3色可染的 证明:(1)→(2)设G是某平面图的一个平面嵌入,G*是其对偶图。则G 也是平面图。由(1),G是点4色可染的。这种点4染色对应有G的一个4 色正常面染色。 2)→(3)设G是简单2边连通3正则平面图,G是其一个平面嵌入。由(2), G有面正常4染色q。用c0=(0,0)c1=(0,1)c2=(10),c3=(11).表示四种颜 色。构造G的一种边染色如下: 对于边e∈E(G),若e是某两个面∫,g的公共边且∫,g在p下的颜色分别 为c,c,则给e染颜色C(e)=c;+c,(mod2) 其中c与c的加法是向量相加,对各分量分别模2。由于G(从而G)是2边 连通的,故G中每条边e都必定是某两个面的公共边,即G的每条边都被染 色,并且这种染色只用到颜色c,c2,cs因co,c;,c2,c3中不同的向量两两作 加法(模2)只能得到c,c2,c3]。此外,由于G是3正则的,故每个顶点u关联 3条边,设这3条边所夹的三个面的色为c;,c,ck(互不相同),则按边的染 色规则,这3条边应分别染上色c+c,c+ck,c+c;,这是三种不同的色。可见 相邻的三边必染不同的色。因此C是G的一种正常的边3染色。 (3)→(1)假设(3)成立。下面用反证法证明(1)。8 定理 7.5.1 设G∗是 G 的对偶图，则 χ χ (G) (G ) ∗ ∗ = 。 证明：由定义立即可知。 四色猜想：任何地图只需用 4 种颜色来染色，就可使得任何具有公共边界的两 个区域染不同的颜色。 四色猜想的图论表述：对任何平面图的平面嵌入 G， χ (G) 4 ∗ ≤ 。 二、四色猜想的几种等价表述 定理 7.5.2 对任何平面图 G， χ(G) 4 ≤ 当且仅当其色多项式 P G( ,4) 0 > 。 证明：由色数和色多项式的定义立即可知。 定理 7.5.3 下列三个命题等价： （1） 每个平面图都是点 4 可染的； （2） 每个平面图的平面嵌入是面 4 可染的； （3） 每个简单 2 边连通 3 正则平面图是边 3 色可染的。 证明：（1）⇒（2）设 G 是某平面图的一个平面嵌入，G∗是其对偶图。则G∗ 也是平面图。由（1），G∗是点 4 色可染的。这种点 4 染色对应有 G 的一个 4 色正常面染色。 （2）⇒（3）设 G 是简单 2 边连通 3 正则平面图，G 是其一个平面嵌入。由(2), G 有面正常 4 染色ϕ 。用 0 12 3 c (0,0), c (0,1),c (1,0), c (1,1) = == = 来表示四种颜 色。构造G 的一种边染色如下： 对于边e EG ∈ ( ) ，若 e 是某两个面 f , g 的公共边且 f , g 在ϕ 下的颜色分别 为 ,i j c c ，则给 e 染颜色 ( ) (mod 2) Ce c c = +i j . 其中 ci与 cj的加法是向量相加，对各分量分别模 2。由于 G（从而G ）是 2 边 连通的，故G 中每条边 e 都必定是某两个面的公共边，即G 的每条边都被染 色，并且这种染色只用到颜色 c1，c2，c3 [因 c0，c1，c2，c3中不同的向量两两作 加法(模 2)只能得到 c1，c2，c3]。此外，由于G 是 3 正则的，故每个顶点 u 关联 3 条边，设这 3 条边所夹的三个面的色为 ci，cj，ck（互不相同），则按边的染 色规则，这 3 条边应分别染上色 ci+ cj，cj+ ck，ck+ci，这是三种不同的色。可见 相邻的三边必染不同的色。因此 C 是G 的一种正常的边 3 染色。 （3）⇒（1）假设（3）成立。下面用反证法证明（1）