第七章平面图 §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)