定理118 定理118:设G是连通平面图,G的各面的 次数至少是(≥3),则 m(n2)(E2) 证明:r=2+mn, 2m==1eg(R)≥/r=/(2+mn) 所以m(n2)(2).# 定理119:设平面图G有p个连通分支,G 的各面的次数至少是(23,则 ms(np-1)(2).# 《集合论与图论》第23讲 16
《集合论与图论》第23讲 16 定理11.8 定理11.8: 设G是连通平面图, G的各面的 次数至少是l(≥3), 则 m≤(n-2)l/(l-2) 证明: r=2+m-n, 2m=Σri=1deg(Ri)≥l•r=l•(2+m-n), 所以 m≤(n-2)l/(l-2). # 定理11.9: 设平面图G有p个连通分支, G 的各面的次数至少是l(≥3), 则 m≤(n-p-1)l/(l-2). #
推论 秦推论:K和Kx23都不是平面图 证明:(反证)假设K和K3都是平面图 (1)K<是简单图,所以=3, 10m(n-2)(2)=(52)3/32)=9,矛盾! 2)K3是偶图无奇圈所以=4, 9=m(n2)(E2)=(6-2)44-2)=8,矛盾!# 鲁 Jordan定理: Jordan曲线(自身不相交封闭曲线) 把平面分为2部分,连接内部与外部点的任意曲 线必然与 Jordan曲线相交 《集合论与图论》第23讲
《集合论与图论》第23讲 17 推论 推论: K5和K3,3都不是平面图. 证明: (反证)假设K5和K3,3都是平面图. (1) K5是简单图, 所以l =3, 10=m≤(n-2)l/(l-2)=(5-2)3/(3-2)=9, 矛盾! (2) K3,3是偶图,无奇圈,所以l =4, 9=m≤(n-2)l/(l-2)=(6-2)4/(4-2)=8, 矛盾! # Jordan定理: Jordan曲线(自身不相交封闭曲线) 把平面分为2部分, 连接内部与外部点的任意曲 线必然与Jordan曲线相交.