定理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)