定理:设G=<V,E>是有限平面图,有r个面, 则所有面的次数之和等于边数的2倍。即 ∑deg()=21E 证明:G的任何一边,或者是两个面的公共边界 为每一个面的次数增加1;或者在一个面中作为边界重 复计算两次,为该面的次数增加2。无论那种情况G的 任何一边为图中面的次数和增加2,故所有面的次数之 和等于边数的2倍
定理：设G=V,E是有限平面图，有r个面， 则所有面的次数之和等于边数的2倍。即 =2|E|。 证明：G的任何一边，或者是两个面的公共边界， 为每一个面的次数增加1；或者在一个面中作为边界重 复计算两次，为该面的次数增加2。无论那种情况G的 任何一边为图中面的次数和增加2，故所有面的次数之 和等于边数的2倍。 1 deg( ) r i i r =
设G为一个平面图,如果在G中任意不相邻 的两个顶点之间再加一条边,所得图为非平面图, 则称G为极大平面图 G 不是平面图
设G为一个平面图, 如果在G中任意不相邻 的两个顶点之间再加一条边, 所得图为非平面图, 则称G为极大平面图。 G G' 不是平面图
关于极大平面图有以下的几个结论: ①极大平面图是连通图。 ②结点数大于等于3的极大平面图不可能 存在割点和桥。 ③设G为结点数大于等于3的简单连通平 面图,G为极大平面图当且仅当G的每个面的次 数均为3
关于极大平面图有以下的几个结论： ①极大平面图是连通图。 ②结点数大于等于3的极大平面图不可能 存在割点和桥。 ③设G为结点数大于等于3的简单连通平 面图, G为极大平面图当且仅当G的每个面的次 数均为3
在非平面图G中任意删除一条边,所得图为平 面图,则称G为极小非平面图 例 G G
在非平面图G中任意删除一条边，所得图为平 面图, 则称G为极小非平面图。 例： G G
定理(欧拉公式):任意连通平面图G,若有n 个结点,m条边和r个面,则欧拉公式n-m+r=2 成立。 证明:对边数ml归纳证明。 (1)设m=0,由于G是连通图,所以G只能 是平凡图。这时,n=1,m=0,r=1,n-mr=2 成立。 (2)设m=k(k1)时欧拉公式成立,下证当 mF=k+1时,欧拉公式也成立
定理 (欧拉公式)：任意连通平面图G，若有n 个结点，m条边和r个面，则欧拉公式n-m+r=2 成立。 证明：对边数m归纳证明。 ⑴设m=0，由于G是连通图，所以G只能 是平凡图。这时，n=1，m=0，r=1，n-m+r=2 成立。 ⑵设m=k (k≥1)时欧拉公式成立，下证当 m=k+1时，欧拉公式也成立