下面证明极大平面图的一个重要性质。 定理1设G是至少有3个顶点的平面图，则G是极大平 面图，当且仅当G的每个面的次数是3且为单图。 注：该定理可以简单记为是“极大平面图的三角形特 征”，即每个面的边界是三角形。 证明：“必要性” 由引理知，G是单图、G无割边。于是G的每个面的 次数至少是3。 假设G中某个面的次数大于等于4。记的边界是 V1V2VV4Vk。如下图所示
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 下面证明极大平面图的一个重要性质。 定理1 设G是至少有3个顶点的平面图，则G是极大平 面图，当且仅当G的每个面的次数是3且为单图。 注：该定理可以简单记为是“极大平面图的三角形特 征”，即每个面的边界是三角形。 证明：“必要性” 由引理知，G是单图、G无割边。于是G的每个面的 次数至少是3。 假设G中某个面f的次数大于等于4。记f的边界是 v1v2v3v4.vk。如下图所示
如果v,与v不邻接，则连接vV3,没有破坏G的平面性， 这与G是极大平面图矛盾。所以vV必须邻接，但必须在 f外连线；同理v,与v4也必须在外连线。但边y13与边 v2Y在f外交叉，与G是平面图矛盾！ 所以，G的每个面次数一定是3. 定理的充分性是显然的
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 如果v1与v3不邻接，则连接v1v3，没有破坏G的平面性， 这与G是极大平面图矛盾。所以v1v3必须邻接，但必须在 f 外连线；同理v2与v4也必须在f外连线。但边v1v3与边 v2v4在 f 外交叉，与G是平面图矛盾！ 所以，G的每个面次数一定是3. 定理的充分性是显然的。 v1 v2 v3 v4 v5 vk f
推论：设G是个点，m条边和个面的极大平面图， 且n≥3.则：(1)m=3n-6;(2)=2n<4. 证明：因为G是极大平面图，所以，每个面的次数为3. 由次数公式： 2m= deg(f)=3 f∈Φ 由欧拉公式： o=2-n+m 所以得： m=2-n+m
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 推论：设G是n个点，m条边和ф个面的极大平面图， 且n≥3.则：(1) m=3n-6; (2) ф=2n-4. 证明：因为G是极大平面图，所以，每个面的次数为3. 由次数公式： 2 deg( ) 3 f m f = = 由欧拉公式： = − + 2 n m 所以得： 2 2 3 m n m = − +
所以得： m=3n-6 又 m=n+0-2 所以： =2n-4 注：顶点数相同的极大平面图并不唯一。例如： 正20面体 非正20面体
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 所以得： m n = − 3 6 又 m n = + − 2 所以： = − 2 4 n 注：顶点数相同的极大平面图并不唯一。例如： 正20面体 非正20面体
还在研究中的问题是：顶点数相同的极大平面图的个 数和结构问题。 与极大平面图相对应的图是极小不可平面图。 2、极大外平面图及其性质 定义2若一个可平面图G存在一种平面嵌入，使得其所 有顶点均在某个面的边界上，称该图为外可平面图。外可 平面图的一种外平面嵌入，称为外平面图。 外可平面图 外平面图1 外平面图2
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 还在研究中的问题是：顶点数相同的极大平面图的个 数和结构问题。 2、极大外平面图及其性质 与极大平面图相对应的图是极小不可平面图。 定义2 若一个可平面图G存在一种平面嵌入，使得其所 有顶点均在某个面的边界上，称该图为外可平面图。外可 平面图的一种外平面嵌入，称为外平面图。 外可平面图 外平面图1 f 外平面图2 f