图92:并不是所有的图都是平面图。(K5和
图9.2：并不是所有的图都是平面图。（ K 5 和 K3,3 ）
9.1平面图与欧拉公式 、欧拉公式 1定义92(面/外部面/内部面) 平面图G嵌入平面后将G分成若干 个连通闭区域,每一个连通闭区域称为G 的一个面 恰有一个无界的面,称为外部面 其余的面称为内部面
9.1 平面图与欧拉公式 二、欧拉公式 1 定义9.2（面/外部面/内部面） 平面图G嵌入平面后将Ğ分成若干 个连通闭区域，每一个连通闭区域称为G 的一个面。 恰有一个无界的面，称为外部面。 其余的面称为内部面
9.1平面图与欧拉公式 2欧拉公式 (1)定理9.1 若连通平面图G有n个顶点,e条边和f 个面,则 n-e+f2 称为欧拉公式。 证明方法:归纳法
9.1 平面图与欧拉公式 2 欧拉公式 （1）定理9.1 若连通平面图G有n个顶点，e条边和f 个面，则 n-e+f=2 称为欧拉公式。 证明方法：归纳法
明 1)归纳基砷:一条边,欧拉公式成立 (2)归纳步骤:假设m-1条边,欧拉公式成立; 考察m条边的连通平面图: 1)若有度数为1的顶点,则删去该顶点及其关联边, 便得到连通平面图G’,G满足欧拉公式,再将删去 的点和边加回G得到G也满足欧拉公式; 2)若没有度数为1的顶点,则删去有界面边界上的 任一边,便得到连通平面图G’,G满足欧拉公式, 再将删去的边加回G'得到G也满足欧拉公式
证明： （1）归纳基础：一条边，欧拉公式成立； （2）归纳步骤：假设m-1条边，欧拉公式成立； 考察m条边的连通平面图： 1）若有度数为1的顶点，则删去该顶点及其关联边， 便得到连通平面图G’，G’满足欧拉公式，再将删去 的点和边加回G’得到G也满足欧拉公式； 2）若没有度数为1的顶点，则删去有界面边界上的 任一边，便得到连通平面图G’， G’满足欧拉公式， 再将删去的边加回G’得到G也满足欧拉公式
9.1平面图与欧拉公式 (2)推论91 若G是n≥3的平面简单图,则e<3n-6。 证明:只证明连通的平面简单图的情况,G是n≥3 的平面简单图,每个面由3条或更多条边围成, 因此边的总数大于等于3,因为每条边至多被 计算两次,所以G中至少有2条边,即e≥32。 根据欧拉公式,有n-e+2e/3≥2 所以3n-6≥e
9.1 平面图与欧拉公式 (2)推论9.1 若G是n3的平面简单图，则e3n-6。 证明：只证明连通的平面简单图的情况，G是n3 的平面简单图，每个面由3条或更多条边围成， 因此边的总数大于等于3f，因为每条边至多被 计算两次，所以G中至少有3f/2条边，即e3f/2。 根据欧拉公式，有n-e+2e/32。 所以3n-6e