***********************************次数的性质定理17.4平面图各面次数之和等于边数的两倍.证对每一条边e,若e在两个面的公共边界上,则在计算这两个面的次数时,e各提供1.而当e只在某一个面的边界上出现时,它必在该面的边界上出现两次,从而在计算该面的次数时,e提供2．*第31页，共57页，星期日，2025年，2月5日极大平面图定义11.8G为简单平面图,若在G的任意两个不相邻的顶点之间加一条边所得图为非平面图,则称G为极大平面图.例如,K5,K33删去一条边后是极大平面图K1,K2,K3,K4都是极大平面图.定理11.10设G为n(n?3)阶简单连通的平面图,G为极大平面图当且仅当G的每个面的次数均为3.证现只证必要性.各面次数都大于或等于3.假如deg(Ri)=s?4,若v1与v3不相邻,则在Ri内加边(v1,v3)不破坏平面性,与G是极大平面图矛盾,因而v1与v3必相邻,且边(v1,v3)必在Ri外部.同样地,v2与v4也相邻且边(v2,v4)在Ri的外部.于是,(v1,v3)与(v2,v4)相交于Ri的外部,与G是平面图矛盾.*第32页，共57页，星期日，2025年，2月5日例是否是极大平面图?定理的应用只有(3)为极大平面图(1)(2)(3)*第33页，共57页，星期日，2025年，2月5日极小非平面图定义11.9若在非平面图G中任意删除一条边,所得图为平面图,则称G为极小非平面图.K5,K3,3都是极小非平面图极小非平面图必为简单图*第34页，共57页，星期日，2025年，2月5日欧拉公式定理11.11设G为n阶m条边r个面的连通平面图,则n?m+r=2证对m做归纳证明.m=0时,G为平凡图,n=1,m=0,r=1,成立.设m=k(k?0)时结论成立.当m=k+1时,分两者情况讨论:(1)G中有一个1度顶点v,令G?=G?v,仍是连通的,n?=n?1,m?=m?1=k,r?=r.由归纳假设,n??m?+r?=2.于是n?m+r=(n?+1)?(m?+1)+r?=n??m?+r?=2(2)G中没有1度顶点,则每一条边都在某两个面的公共边界上.任取一条边e,令G?=G?e,仍连通且n?=n,m?=m?1=k,r?=r?1.由归纳假设,n??m?+r?=2.于是n?m+r=n??(m?+1)+(r?+1)=n??m?+r?=2*第35页，共57页，星期日，2025年，2月5日欧拉公式的推广推论对于有k个连通分支的平面图G,有n?m+r=k+1其中n,m,r分别为G的顶点数,边数和面数.证设G的连通分支为G1,G2,…,Gk,由欧拉公式ni?mi+ri=2,i=1,2,…,k.G的面数.于是，整理得n?m+r=k+1*第36页，共57页，星期日，2025年，2月5日解得与欧拉公式有关的定理定理11.12设G为连通的平面图,每个面的次数至少为l?3，则证由定理11.9及欧拉公式,定理11.13K5,K3,3都是非平面图.证假设K5是平面图,K5无环和平行边,每个面的次数均大于等于3.应该有矛盾.*第37页，共57页，星期日，2025年，2月5日证(续)假设K3,3是平面图,K3,3中最短圈的长度为4,每个面的次数均大于等于4.应该有矛盾.定理11.14设G为n(n?3)阶m条边的极大平面图,则m=3n?6.证极大平面图是连通图,由欧拉公式得r=2+m?n.又由定理11.10的必要性,G的每个面的次数均为3,所以2m=3r.得m=3n?6．推论设G是n(n?3)阶m条边的简单平面图,则