第七章平面图 §7.1平面图的概念 定义7.1.1如果图G能画在曲面S上,使得任意两边互不交叉,则称G可嵌入 曲面S。若图G可嵌入平面,则称G是可平面图或平面图,画出的无交叉边的 图形称为图G的平面嵌入。 例如,下面是三个平面图及其平面嵌入。 根据定义,下列定理是显然的。 定理71.1若图G是平面图,则G的任何子图都是平面图。 定理712若图G是非平面图,则G的任何母图都是非平面图 定理713若图G是平面图,则在G中添加重边或环边后所得之图仍是平面图。 注:由以上定理知 (1)Kn(n≤4)和K1,n(≥1)及其所有子图都是平面图 (2)环边和重边不影响图的平面性。故以下讨论平面性时总假定图G是简单图。 定义712设图G是平面图(已平面嵌入),G的边将平面划分出的若干区域都称 为图G的面。其中面积无限的面称为无限面或外部面,面积有限的面称为有限 面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为 该面的次数(割边按两次计),面R的次数记为deg(R)。 定理714平面图G中所有面的次数之和等于G的边数的两倍,即 ∑e(R)=2a(O 其中R1,R2,…,R是G的所有面。 证明:对G的任何一条边e,若e是两个面R1和的公共边界,则在计算R 和B,的次数时,e各提供了1:若e只是某一个面的边界,则在计算该面的次 数时,e提供了2。可见每条边在计算总次数时,都提供2。因而结论成
1 第七章 平面图 §7.1 平面图的概念 定义 7.1.1 如果图 G 能画在曲面 S 上，使得任意两边互不交叉，则称 G 可嵌入 曲面 S。若图 G 可嵌入平面，则称 G 是可平面图或平面图，画出的无交叉边的 图形称为图 G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理 7.1.1 若图 G 是平面图，则 G 的任何子图都是平面图。 定理 7.1.2 若图 G 是非平面图，则 G 的任何母图都是非平面图。 定理 7.1.3 若图 G 是平面图, 则在 G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) Kn ( n≤4 ) 和 K1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图 G 是简单图。 定义 7.1.2 设图 G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称 为图 G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限 面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为 该面的次数 (割边按两次计)，面 R 的次数记为 deg(R)。 定理 7.1.4 平面图 G 中所有面的次数之和等于 G 的边数的两倍，即 其中 R1, R2, … , Rr 是 G 的所有面。 证明： 对 G 的任何一条边 e，若 e 是两个面 Ri 和 Rj 的公共边界，则在计算 Ri 和 Rj 的次数时，e 各提供了 1；若 e 只是某一个面的边界，则在计算该面的次 数时，e 提供了 2。可见每条边在计算总次数时，都提供 2。因而结论成立。 1 deg( ) 2 ( ). r i i R Gε = ∑ =
定义7.1.3设G为简单平面图,若在G的任意不相邻的顶点,v之间加边 后,所得之图成为非平面图,则称G是极大平面图。 易见K1,K2,K3,K4,K5-e都是极大平面图。 定义71.4若非平面图G任意删除一条边后,所得之图都是平面图,则称G为 极小非平面图。 容易证明下列定理 定理715极大平面图是连通的 定理71.6n阶(n≥3)极大平面图中没有割边和割点 §72欧拉公式 定理721(欧拉公式)设G是连通的平面图,n,m,r分别是其顶点数、边数和 面数,则 n-m+r=2 证明:对边数m作数学归纳法。 当m=0时,因G是连通图,所以G只能是平凡图,结论显然成立。 假设当m=k时,结论成立。下面证明m=k+1的情况。 若G是树,则G至少有两片树叶。设ν是G的一片树叶。令G′=G-ν,则 G仍是连通图,且G的边数m′=m-1=k,由归纳假设知,nm+r′=2,而n′=n-1 r'=r,于是 n-m+r=(m+1)-(m'+1)+r′=nm+r′=2。 若G不是树,则G中含有圈。设边e在G的某个圈上。令G′=G-e,则G′ 仍是连通图,且G的边数m′=m-1=k,由归纳假设知 n′m′+r′=2,而n′=n,r′=r-1, 于是 n-m+r=n'-(m′+1)+(r1)=n-m+r′=2 证毕 定理72(欧拉公式的推广形式)对于具有v(w≥1)个连通分支的平面图G,有 其中n,m,r分别是其顶点数、边数和面数。 证明:设G的连通分支分别为G1G2,…,G1,并设G1的顶点数、边数和面数 分别为n12m1F°由欧拉公式可知 2
2 定义 7.1.3 设 G 为简单平面图，若在 G 的任意不相邻的顶点 u, v 之间加边 uv 后，所得之图成为非平面图，则称 G 是极大平面图。 易见 K1, K2, K3, K4, K5– e 都是极大平面图。 定义 7.1.4 若非平面图 G 任意删除一条边后，所得之图都是平面图，则称 G 为 极小非平面图。 容易证明下列定理 定理 7.1.5 极大平面图是连通的。 定理 7.1.6 n 阶（ n ≥ 3）极大平面图中没有割边和割点。 §7.2 欧拉公式 定理 7.2.1（欧拉公式）设 G 是连通的平面图，n, m, r 分别是其顶点数、边数和 面数，则 n – m + r = 2。 证明：对边数 m 作数学归纳法。 当 m=0 时，因 G 是连通图，所以 G 只能是平凡图，结论显然成立。 假设当 m=k 时，结论成立。下面证明 m=k+1 的情况。 若 G 是树，则 G 至少有两片树叶。设 v 是 G 的一片树叶。令 G′ =G− v，则 G′ 仍是连通图, 且 G′ 的边数 m′ =m−1=k, 由归纳假设知, n′–m′ +r′ =2, 而 n′ =n−1, r′ =r, 于是 n – m + r = (n′ +1) – (m′ +1) + r′ = n′–m′ +r′ = 2。 若 G 不是树，则 G 中含有圈。设边 e 在 G 的某个圈上。令 G′ =G− e，则 G′ 仍是连通图，且 G′ 的边数 m′ =m−1=k ，由归纳假设知 n′–m′ +r′ = 2, 而 n′ =n, r′ =r −1 ， 于是 n – m + r = n′ – (m′ +1) + (r′+1) = n′–m′ +r′ = 2 。 证毕。 定理 7.2.2（欧拉公式的推广形式）对于具有 w(w ≥ 1)个连通分支的平面图 G, 有 n – m + r = w+1。 其中 n, m, r 分别是其顶点数、边数和面数。 证明：设 G 的连通分支分别为 G1, G2, …, Gw，并设 Gi 的顶点数、边数和面数 分别为 ni , mi , ri 。由欧拉公式可知
1-m+F=2,(=1,2,…v) 易知m=∑m,n=∑n,由于G的每个分支有一个外部面,而G只有一个外部面 故G的面数r=∑-+1,于是 2w=∑(n-m+)=∑n-∑m+∑=n-m+r+-1 整理即得结论 证毕. 定理723设G是连通的平面图,且每个面的次数至少为l(≥3),则G的边数 m与顶点数n有如下关系 (n-2) 证明:由定理714可知 2m=∑deg(R)2lr 由欧拉公式可知r=2+m-n.将此式代入上式,得2m≥l(2+m-m),整理便得 结论。证毕 推论721K和K,都不是平面图。 证明:若K3是平面图,由于K5中无环边和重边,故每个面的次数至少为3, 而K的边数为10。由定理723,应有10≤ 3(5-2)=9,这是不可能的。因 此K不是平面图。 若K3是平面图,由于K3中最短圈的长度为4,故每个面的次数至少为 4,而K22的边数为9。由定理723,应有9≤(6-2)=8,这是不可能的 因此K,不是平面图。证毕 推论722Kn(n≥5)和K3n(n≥3)都不是平面图 证明:由定理712和推论72.1立即可知。 推论723K和K33都是极小非平面图 由推论721和极小非平面图的定义容易验证 定理74设G是具有w(≥)个连通分支的平面图,各面的次数至少为ll23), 则G的边数m与顶点数n有如下关系: 证明:利用欧拉公式的推广形式(定理722),与上一定理类似可证
3 定理 7.2.3 设 G 是连通的平面图，且每个面的次数至少为 l (l ≥ 3)，则 G 的边数 m 与顶点数 n 有如下关系： ( 2). 2 l m n l ≤ − − 证明：由定理 7.1.4 可知 推论 7.2.1 K5 和 K3,3 都不是平面图。 证明：若 K5 是平面图，由于 K5 中无环边和重边，故每个面的次数至少为 3， 而 K5 的边数为 10。由定理 7.2.3，应有 , 这是不可能的。因 此 K5不是平面图。 若 K3,3 是平面图，由于 K3,3 中最短圈的长度为 4，故每个面的次数至少为 4，而 K3,3的边数为 9。由定理 7.2.3，应有 , 这是不可能的。 因此 K3,3不是平面图。证毕。 推论 7.2.2 Kn (n ≥ 5)和 K3,n (n ≥ 3)都不是平面图。 证明：由定理 7.1.2 和推论 7.2.1 立即可知。 推论 7.2.3 K5 和 K3,3都是极小非平面图。 由推论 7.2.1 和极小非平面图的定义容易验证。 定理 7.2.4 设 G 是具有 w(w≥1)个连通分支的平面图, 各面的次数至少为 l(l ≥3)， 则 G 的边数 m 与顶点数 n 有如下关系： 证明：利用欧拉公式的推广形式(定理 7.2.2)，与上一定理类似可证。 1 1 1 1 11 1 2, ( 1, 2, ). ,. , , 1, 2( ) 1 i ii w w i i i i w i i w ww w i ii i i i i ii i nmr i w m mn n G G G r rw w n m r n m r nmrw = = = = == = − += = = = = −+ = − + = − + = − ++ − ∑ ∑ ∑ ∑ ∑∑ ∑ " 易知 由于 的每个分支有一个外部面 而 只有一个外部面 故 的面数 于是 整理即得结论. 证毕. 1 2 deg( ) 2 . , 2 (2 ), r i i m R lr r mn ml mn = = ≥⋅ =+ − ≥ + − ∑ 由欧拉公式可知 将此式代入上式 得 整理便得 结论。证毕。 3 10 (5 2) 9 3 2 ≤ − = − 4 9 (6 2) 8 4 2 ≤ − = − ( 1). 2 l m nw l ≤ − − −
定理725设G是具有m条边的m(n≥3)阶简单平面图,则m≤3n-6。 证明:设G有w(w≥1)个连通分支。若G为树或森林,则m=n-w≤3n-6。 否则,G中必有圈。因G是简单图,所以各圈的长度至少是3,从而G中面的 最小次数1≥3。又因函数 在l=3时达到最大值3,于是由定理724, /(n--)s3m-2)=3m-6 证毕。 定理72.6具有m条边的m(n≥3)阶简单连通的平面图G是极大平面图当且仅 当G的每个面的次数均为3。 证明:充分性:由定理714知,2m=∑deg(R)=3因G是连通的,由欧拉 公式可知,r=2+mn。由此二式整理得:m=3n6 假如G不是极大平面图,则G中一定存在不相邻的顶点u和ν,使得G′ G+仍是简单平面图,而G的边数m′=m+1,n′=n,结合m=3n6得:m 3n′-5>3n′-6。这与定理725矛盾 必要性设G是简单、连通的极大平面图,则G中无环边和重边,且由定理 71.6可知,G中无割边和割点。于是G中各面的次数至少为3。以下用反证法 证明G中各面的次数不会大于3。从而使必要性得证 事实上,假如G的某个面R的次数deg(R)=s≥4,则R的边界上至少有4 个顶点,设其中4个依次相邻的顶点为v1,n2,v3,v4。若v1与v在G中不相邻, 则在R内添加边v13不破坏平面性,这与G是极大平面图矛盾。因而v与v3 在G中必定相邻。但因面R的存在,边v1v必在R的外边。类似地,n与v4在 G中也必定相邻且边v2V4必在R的外边。于是边v3与边v24必在R的外部相 交。这与G是平面图矛盾。从而G中各面的次数不会大于3。证毕。 由该定理可知,下列平面图中,只有(c)是极大平面图 (a)
4 定理 7.2.5 设 G 是具有 m 条边的 n(n≥3) 阶简单平面图，则 m ≤ 3n−6 。 证明：设 G 有 w (w≥1) 个连通分支。若 G 为树或森林，则 m = n − w ≤ 3 n− 6 。 否则，G 中必有圈。因 G 是简单图，所以各圈的长度至少是 3，从而 G 中面的 最小次数 l ≥ 3 。又因函数 在 l=3 时达到最大值 3，于是由定理 7.2.4, 证毕。 定理 7.2.6 具有 m 条边的 n(n ≥ 3) 阶简单连通的平面图 G 是极大平面图当且仅 当 G 的每个面的次数均为 3。 证明：充分性：由定理 7.1.4 知， 。因 G 是连通的，由欧拉 公式可知，r =2+m–n。由此二式整理得： m =3n–6 。 假如 G 不是极大平面图，则 G 中一定存在不相邻的顶点 u 和 v，使得 G′ =G+uv 仍是简单平面图，而 G′ 的边数 m′ =m+1, n′ =n, 结合 m =3n–6 得： m′ = 3n′ – 5> 3n′ – 6 。这与定理 7.2.5 矛盾。 必要性 设 G 是简单、连通的极大平面图，则 G 中无环边和重边，且由定理 7.1.6 可知，G 中无割边和割点。于是 G 中各面的次数至少为 3。以下用反证法 证明 G 中各面的次数不会大于 3。从而使必要性得证。 事实上，假如 G 的某个面 Ri的次数 deg(Ri)=s ≥ 4，则 Ri的边界上至少有 4 个顶点，设其中 4 个依次相邻的顶点为 v1, v2, v3, v4。若 v1与 v3在 G 中不相邻， 则在 Ri 内添加边 v1v3 不破坏平面性，这与 G 是极大平面图矛盾。因而 v1 与 v3 在 G 中必定相邻。但因面 Ri的存在，边 v1v3必在 Ri的外边。类似地，v2与 v4在 G 中也必定相邻且边 v2v4必在 Ri的外边。于是边 v1v3与边 v2v4必在 Ri的外部相 交。这与 G 是平面图矛盾。从而 G 中各面的次数不会大于 3。 证毕。 由该定理可知，下列平面图中，只有(c)是极大平面图。 2 1 2 2 l l l = + − − ( 1) 3( 2) 3 6. 2 l m nw n n l ≤ −−≤ − = − − 1 2 deg( ) 3 r i i m Rr = = ∑ = (a) (c) (b)
定理727设G是具有m条边的n(n≥3)阶极大平面图,则m=3n=6。 证明:由于极大平面图是连通图,由欧拉公式,r=2+mn。又因G是极大平面 图,由定理726可知,G的每个面的次数均为3,故 2m=∑deg(R)=3r 由以上两式整理即得:m=3n6。证毕。 定理7.8设G是具有m条边的n(n≥3)阶简单平面图,则G的最小度δ≤5 证明:若G的阶数n≤6,则结论显然成立,下设n≥7。假若δ≥6,则 2m=∑d()≥6n 因而m≥3n,这与定理72.5矛盾。证毕。 §73平面图的判断 定义73.1设e=w是图G的一条边。在G中删除e,并添加新点w,令u和v 均与w相邻,这个过程称为在G中插入2度顶点w;反之,设w为G中一个2 度顶点,设它的两个邻点为u和ν,删除v并添加新边,这个过程称为在G 中消去2度顶点w 定义732若两个图G1和G2同构,或者G1和G2经过反复插入或消去2度顶点 后同构,则称G1和G2是同胚的。 例如,下列(a)与K3同胚,(b)与K4同胚。 下列两个定理是平面图判定定理,证明从略 定理731(库拉托夫斯基定理1)图G是平面图当且仅当G中既不含与K5同胚 的子图,也不含与K3同胚的子图 定理732(库拉托夫斯基定理2)图G是平面图当且仅当G中既没有可收缩到 Ks的子图,也没有可收缩到K33的子图
5 定理 7.2.7 设 G 是具有 m 条边的 n (n ≥ 3) 阶极大平面图，则 m=3n–6。 证明：由于极大平面图是连通图，由欧拉公式, r=2+m–n。 又因 G 是极大平面 图，由定理 7.2.6 可知，G 的每个面的次数均为 3，故 由以上两式整理即得： m=3n–6 。证毕。 定理 7.2.8 设 G 是具有 m 条边的 n (n ≥ 3) 阶简单平面图，则 G 的最小度 δ ≤ 5。 证明：若 G 的阶数 n ≤ 6 ，则结论显然成立，下设 n ≥ 7 。假若 δ ≥ 6，则 因而 m ≥ 3n，这与定理 7.2.5 矛盾。证毕。 §7.3 平面图的判断 定义 7.3.1 设 e = uv 是图 G 的一条边。在 G 中删除 e，并添加新点 w，令 u 和 v 均与 w 相邻，这个过程称为在 G 中插入 2 度顶点 w；反之，设 w 为 G 中一个 2 度顶点，设它的两个邻点为 u 和 v，删除 w 并添加新边 uv，这个过程称为在 G 中消去 2 度顶点 w。 定义 7.3.2 若两个图 G1和 G2同构，或者 G1和 G2经过反复插入或消去 2 度顶点 后同构，则称 G1和 G2是同胚的。 例如，下列(a)与 K3 同胚，(b)与 K4 同胚。 下列两个定理是平面图判定定理，证明从略。 定理 7.3.1 (库拉托夫斯基定理 1) 图 G 是平面图当且仅当 G 中既不含与 K5 同胚 的子图，也不含与 K3,3 同胚的子图。 定理 7.3.2 (库拉托夫斯基定理 2) 图 G 是平面图当且仅当 G 中既没有可收缩到 K5 的子图，也没有可收缩到 K3,3的子图。 1 2 deg( ) 3 r i i m Rr = = = ∑ 1 2 ( ) 6. n i i m dv n = = ≥ ∑ (a) (b)
§74平面图的对偶图 定义741设G是平面图的某个平面嵌入,G的对偶图G*构造如下: 在G的面R中放置G*的顶点v*。设e为G的任意一条边,若e在G的 面R与R的公共边界上,做G*的边e*与e相交,且e*关联G*的位于R和R 中的顶点w*与哮*,即e*=w*y*,e*不与其它任何边相交。若e为G中的割边 且在面R的边界上,则e*是以R中G*的顶点w*为端点的环,即e*=v*y*。 简单的说,平面图G的对偶图G*就是以G的面作为顶点的图:用顶点代 表G的各个面,两个面有k条公共边界,则相应的顶点间连k条边。若某个面 中含有割边,则该面相应的点上连一条环边。 从定义不难看出G的对偶图G*有以下性质: (1)G*是平面图,而且是平面嵌入 (2)G*是连通图。 (3)若边e为G中的环边,则G*与e对应的边e*为割边;反之,若e为割 边,则G*中与e对应的边e*为环边。 (4)在多数情况下,G*为含重边的图。 (5)同构的平面图(平面嵌入)的对偶图不一定是同构的。 例如,下列两图(实线边的图)是同构的,但它们的对偶图(虚线所示) 不同构,因为两个对偶图中环边所关联的顶点的度不相等 平面图G与它的对偶图G*的顶点数、边数和面数有如下关系。 定理741设G*是连通平面图G的对偶图,n*,m*r*和n,m,r分别为G*和G 的顶点数、边数和面数,则 (1)n*= (2)m (4)设G*的顶点v*位于G的面R中,则dG(v*)=deg(R) 证明:由G*的构造可知,(1)和(2)是显然的。 (3)由于G与G*都连通,因而满足欧拉公式 n-m+r=2,n*一m*十r*=2
6 §7.4 平面图的对偶图 定义 7.4.1 设 G 是平面图的某个平面嵌入，G 的对偶图 G* 构造如下： 在 G 的面 Ri中放置 G* 的顶点 vi*。设 e 为 G 的任意一条边，若 e 在 G 的 面 Ri与 Rj的公共边界上，做 G* 的边 e*与 e 相交，且 e* 关联 G* 的位于 Ri和 Rj 中的顶点 vi*与 vj*，即 e*= vi*vj*，e* 不与其它任何边相交。若 e 为 G 中的割边 且在面 Ri 的边界上，则 e*是以 Ri中 G* 的顶点 vi*为端点的环，即 e* = vi*vi* 。 简单的说，平面图 G 的对偶图 G* 就是以 G 的面作为顶点的图：用顶点代 表 G 的各个面，两个面有 k 条公共边界，则相应的顶点间连 k 条边。若某个面 中含有割边，则该面相应的点上连一条环边。 从定义不难看出 G 的对偶图 G* 有以下性质： (1) G* 是平面图，而且是平面嵌入。 (2) G*是连通图。 (3) 若边 e 为 G 中的环边，则 G* 与 e 对应的边 e* 为割边；反之，若 e 为割 边，则 G* 中与 e 对应的边 e* 为环边。 (4) 在多数情况下， G*为含重边的图。 (5) 同构的平面图（平面嵌入）的对偶图不一定是同构的。 例如，下列两图（实线边的图）是同构的，但它们的对偶图（虚线所示） 不同构，因为两个对偶图中环边所关联的顶点的度不相等. 平面图 G 与它的对偶图 G*的顶点数、边数和面数有如下关系。 定理 7.4.1 设 G*是连通平面图 G 的对偶图, n*, m*, r* 和 n, m, r 分别为 G*和 G 的顶点数、边数和面数， 则 (1) n* = r; (2) m* = m; (3) r* = n ; (4) 设 G*的顶点 vi* 位于 G 的面 Ri中，则 dG′(vi* )=deg(Ri )。 证明：由 G* 的构造可知，(1)和(2)是显然的。 (3) 由于 G 与 G* 都连通，因而满足欧拉公式： n－ m＋r = 2， n*－ m*＋r* = 2
由此及上述(1)、(2),便得 2+m-n'=2+m (4)设G的面R的边界为C;。设C中有k条割边(k≥0),k2条非割边,则C 的长度为k2+2k,即deg(R)=k2+2k1。与G中这k条割边对应,在G*中v*处 有k1个环边,而C的k2条非割边对应G*中从v*处引出k2条边,所以 d(vi)=k2+2k,=deg(r,) 定理742设G是具有w个连通分支的平面图G的对偶图, 则(1) (2)m*=m; (3)r*=n-w+1; (4)设v*位于G的面R1中,则dg*v1*)=deg(R1)。 其中n*,m*,r*,n,m,r同前。 证明留作练习。 §7平面图的面染色和四色猜想 平面图的面染色 定义751平面图的平面嵌入G的面正常k染色( proper face k- colouring)是指 k种颜色1,2,…k在G的面集合F(G)上的一种分配,使得有公共边的面所染颜 色不同。用映射的观点看,G的面正常k染色是一个映射 c:F(G)→{l,2,…,k}, 使得对每个i(i=12,…,k),c-(i)内的面两两无公共边。 注:若令F=c-()=f∈F(G)()=1},(=12…,k),则G的一个面正常k 染色可看成是对面集合的一种划分c=(F,F2,…F),其中每个F中的面彼此 不相邻(无公共边) 定义752若平面图的平面嵌入G存在一种面正常k染色,则称G是面k色可 染的( face k-colourable)。 定义753正整数z(G)=min{G面k色可染的}称为G的面色数ace chromatic number) 例如,x'(K4)=4。 7
7 由此及上述（1）、（2），便得 (4) 设 G 的面 Ri的边界为 Ci 。设 Ci 中有 k1条割边(k1≥0)，k2条非割边，则 Ci 的长度为 k2+2k1, 即 deg(Ri) = k2+2k1。与 G 中这 k1条割边对应，在 G* 中 vi*处 有 k1个环边，而 Ci 的 k2条非割边对应 G* 中从 vi* 处引出 k2条边，所以 定理 7.4.2 设 G *是具有 w 个连通分支的平面图 G 的对偶图， 则 (1) n* = r ; (2) m* = m; (3) r* = n－ w＋1; (4) 设 vi * 位于 G 的面 Ri 中，则 dG*(vi * )=deg(Ri )。 其中 n*, m*, r* , n, m, r 同前。 证明留作练习。 §7.5 平面图的面染色和四色猜想 一、平面图的面染色 定义 7.5.1 平面图的平面嵌入 G 的面正常 k 染色（proper face k- colouring）是指 k 种颜色1, 2, , " k 在 G 的面集合 F(G)上的一种分配，使得有公共边的面所染颜 色不同。用映射的观点看，G 的面正常 k 染色是一个映射 c FG k : ( ) {1, 2, , } → " ， 使得对每个 i (i = 1,2,", k ), ) ( 1 c i − 内的面两两无公共边。 注：若令 1 ( ) { ( ) ( ) }, ( 1, 2, , ) Fi c i f FG c f i i k − = =∈ = = " ，则 G 的一个面正常 k 染色可看成是对面集合的一种划分 1 2 (, , , ) k c FF F = " ，其中每个 Fi中的面彼此 不相邻（无公共边）。 定义 7.5.2 若平面图的平面嵌入 G 存在一种面正常 k 染色，则称 G 是面 k 色可 染的（face k-colourable）。 定义 7.5.3 正整数 χ ( ) min{ G kG ∗ = 面 k 色可染的}称为 G 的面色数 (face chromatic number)。 例如， 4 χ ()4 K∗ = 。 r m n mrn 2 2. ∗ ∗∗ =+ − =+ −= * * 2 1 ( ) 2 deg( ). G i i dv k k R =+ =
定理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）
若存在一个平面图G不能用4种色正常染色,则其色数至少为5。设G是 G的一个平面嵌入,则存在一个三角剖分图H,使得G是H的生成子图(留作 习题),H的对偶图H是2边连通3正则的简单图(留作习题)。由(3), H是边3色可染的。设c=(E1E2,E3)是H的一个边正常3染色。对于i≠j 设H=H[E∪E,(只有H12,H3,H23三种)。因H中每个顶点都是3度 的,故染色c的每种颜色都在H'的每个顶点处出现,因而H”的每个顶点都是2 度的,这样的图是边不相交的圈的并。 2 f H 容易证明此时H是面2色可染的。令 q:F(H12)→{a,B;2:F(H13)→>{,5} 分别是H2和H3的正常面2染色。于是H的每个面是H2的某个面与H的某 个面的交集的一部分。所以在和2下,面∫获得两种颜色x和y,记为(x,y), 其中x=a或B,y=y或δ。定义四种新的颜色(a,y),(a,),(B,y),(B,)。易见 H的每个面被这四种颜色之一所染。由于H=H2∪H13,而且H的相邻两个 面得到的颜色对不会相同,所以得到了H的一个面正常4染色。因G是H的生 成子图,故5=x(G)=x(G)≤x(H)=x'(H)≤4,这是不可能的。 (a,y)(B,y) 这两个定理给出了四色猜想的四种等价表述 (1)面染色表述:对任何平面图的平面嵌入G,x'(G)≤4 (2)点染色表述:对任何平面图G,z(G)≤4。 (3)边染色表述:每个简单2边连通3正则平面图是边3色可染的。 (4)色多项式表述:对任何平面图G,色多项式P(G,4)>0
9 若存在一个平面图 G 不能用 4 种色正常染色，则其色数至少为 5。设G 是 G 的一个平面嵌入，则存在一个三角剖分图 H，使得G 是 H 的生成子图（留作 习题），H 的对偶图H∗ 是 2 边连通 3 正则的简单图（留作习题）。由（3）， H∗ 是边 3 色可染的。设 123 c EEE = ( , , )是 H∗ 的一个边正常 3 染色。对于i j ≠ ， 设 [ ], H HE E ij i j ∗ ∗ = ∪ （只有 H ,H ,H 12 13 23 三种）。因 H∗ 中每个顶点都是 3 度 的，故染色 c 的每种颜色都在H∗ 的每个顶点处出现，因而 Hij ∗ 的每个顶点都是 2 度的，这样的图是边不相交的圈的并。 容易证明此时 Hij ∗ 是面 2 色可染的。令 1 12 2 13 ϕ FH FH ( ) {, } ( ) {, } αβ ϕ γδ ： ；： ∗ ∗ → → 分别是H12 ∗ 和 H13 ∗ 的正常面 2 染色。于是 H∗ 的每个面是 H12 ∗ 的某个面与H13 ∗ 的某 个面的交集的一部分。所以在ϕ1 2 和ϕ 下，面 f 获得两种颜色 x 和 y , 记为(x, y)， 其中 x y = = α或， 或 β γδ 。定义四种新的颜色( , ), ( , ), ( , ), ( , ) α γ αδ βγ βδ 。易见 H∗ 的每个面被这四种颜色之一所染。由于HH H 12 13 ∗ ∗ ∗ = ∪ ，而且H∗ 的相邻两个 面得到的颜色对不会相同，所以得到了H∗ 的一个面正常 4 染色。因G 是 H 的生 成子图，故5 (G) (G) (H) (H ) 4 χχχχ∗ ∗ ==≤= ≤ ，这是不可能的。 这两个定理给出了四色猜想的四种等价表述： (1) 面染色表述：对任何平面图的平面嵌入 G， χ (G) 4 ∗ ≤ 。 (2) 点染色表述：对任何平面图 G， χ(G) 4 ≤ 。 (3) 边染色表述：每个简单 2 边连通 3 正则平面图是边 3 色可染的。 (4) 色多项式表述：对任何平面图 G，色多项式 P G( , 4) 0 > 。 3 1 1 3 3 3 2 2 2 1 2 1 H* H* 12 1 1 2 2 2 1 2 1 f2 f3 f1 (,) α γ (,) β γ (,) α δ
三、五色定理 定理7.54(五色定理, Heawood,1890)对于任何平面图G,z(G)≤5。 证明:因为重边不影响点色数,故无妨设图G是平面简单图。对顶点数v作数 学归纳。 v≤5时,定理结论显然成立 假设对v≤n-1的所有平面图,定理结论都成立。考虑v=n的情形 由定理72.8,存在v∈V(G),使得d(v)≤5 (1)若d(v)≤4,考虑G-V0。由归纳假设,x(G-v)≤5。再给v染上 与其邻点(不多于四个)相异的第五种色即可 (2)若d(v)=5,设v1,v2,n2V4,v3是wo的邻点。将它们按逆时针顺序画 在平面上,记G0=G-。由归纳假设,G0可用五种色正常染色。设顶点v1,2, v3,v4,vs在G0中分别染以色a,b,c,d,e。可以假定这五种色互不相同(如果v, V2,v3,V4,V中有染相同色的顶点,则可用第五种色给v染色)。用Gc表示Go 中染a色和染c色的顶点导出的子图。 i)若v与v3分别在Gac的两个连通分支中,则在含有v1的连通分支中将颜 色a,c互换,这样便可给顶点v染色a,从而得到G的一个点正常5染色 i)若v与v在Ga的同一个连通分支中,则存在一个(v1,v3)路P,在P上 顶点的色a,c交替出现。从图G中来看,Ww1+P+13w是一个圈。由于G已嵌 入平面,故n2与v4必分别处在该圈的内、外,因此在G0中由b、d两色导出的 子图Gh中,n2与v4分属于两个连通分支。(否则,在Gb中有(v2,v4)路P, 它与路P相交于一个公共顶点u,由于u在P′上,故应染有颜色b或d,u也 在P上,又应染有颜色a或c,这是不可能的)。无妨设v2处在圈内,这时可 将v2所在的连通分支中b色与d色对换,再给w染上颜色b,这样便可得到G 的一个点正常5染色。证毕
10 三、五色定理 定理 7.5.4 (五色定理，Heawood，1890) 对于任何平面图 G， χ(G) 5 ≤ 。 证明：因为重边不影响点色数，故无妨设图 G 是平面简单图。对顶点数ν 作数 学归纳。 ν ≤ 5时，定理结论显然成立。 假设对ν ≤ − n 1的所有平面图，定理结论都成立。考虑ν = n的情形。 由定理 7.2.8，存在 0 0 v VG dv ∈ ≤ () () 5 ，使得 。 （1）若 0 d v() 4 ≤ ，考虑 G−v0。由归纳假设， 0 χ( )5 G v − ≤ 。再给 v0染上 与其邻点（不多于四个）相异的第五种色即可。 （2）若 0 d v( ) = 5 ，设 v1, v2, v3, v4, v5是 v0的邻点。将它们按逆时针顺序画 在平面上，记 G0 = G−v0。由归纳假设，G0可用五种色正常染色。设顶点 v1, v2, v3, v4, v5在 G0中分别染以色 a, b, c, d, e。可以假定这五种色互不相同（如果 v1, v2, v3, v4, v5中有染相同色的顶点，则可用第五种色给 v0染色）。用 Gac表示 G0 中染 a 色和染 c 色的顶点导出的子图。 i）若 v1与 v3分别在 Gac的两个连通分支中，则在含有 v1的连通分支中将颜 色 a, c 互换，这样便可给顶点 v0染色 a，从而得到 G 的一个点正常 5 染色。 ii）若 v1与 v3在 Gac的同一个连通分支中，则存在一个(v1, v3)路 P，在 P 上 顶点的色 a, c 交替出现。从图 G 中来看，v0 v1+P+ v3 v0是一个圈。由于 G 已嵌 入平面，故 v2与 v4必分别处在该圈的内、外，因此在 G0中由 b、d 两色导出的 子图 Gbd中，v2与 v4分属于两个连通分支。（否则，在 Gbd中有(v2, v4)路 Pˊ， 它与路 P 相交于一个公共顶点 u，由于 u 在 Pˊ上，故应染有颜色 b 或 d，u 也 在 P 上，又应染有颜色 a 或 c，这是不可能的）。无妨设 v2处在圈内，这时可 将 v2所在的连通分支中 b 色与 d 色对换，再给 v0染上颜色 b，这样便可得到 G 的一个点正常 5 染色。证毕。 b v2 v0 v3 v4 v5 a c d e v1