平面嵌入 定理4.平面嵌入图G中所有面的次数之和等于边数m的两倍,即 ∑=.deg(R)=2m,其中r为G的面数 证明: 对于任意的e∈E(G),分以下情况考虑 若e为面R和R付≠的公共边界上的边时,在计算R和R的次 数时,e各被计算1次 当e只在某一个面的边界上出现时,则在计算该面的次数时,e 被计算2次; 所以,每条边在计算总次数时,都被计算2次 因此,∑=1.deg(R=2m
6 平面嵌入 定理4. 平面嵌入图G中所有面的次数之和等于边数m的两倍, 即 Σi=1..rdeg(Ri) = 2m, 其中r为G的面数. 证明: 对于任意的e∈E(G), 分以下情况考虑: 若e为面Ri和Rj(i ≠ j)的公共边界上的边时, 在计算Ri和Rj的次 数时, e各被计算1次; 当e只在某一个面的边界上出现时, 则在计算该面的次数时, e 被计算2次; 所以, 每条边在计算总次数时, 都被计算2次。 因此, Σi=1..rdeg(Ri) = 2m
极大平面图 定义3.设G为简单平面图,若在G的任意不相邻的顶点U,V之间加 边(uv),所得图为非平面图,则称G为极大平面图。 定理5.极大平面图是连通的 定理6.设G是n(n≥3)阶极大平面图,则G中不可能存在割点和桥
7 极大平面图 定义3. 设G为简单平面图, 若在G的任意不相邻的顶点u, v之间加 边(u, v), 所得图为非平面图, 则称G为极大平面图。 定理5. 极大平面图是连通的。 定理6. 设G是n(n ≥ 3)阶极大平面图, 则G中不可能存在割点和桥
极大平面图 定理7.设G为n(n≥3阶简单连通的平面图,G为极大平面图,当且仅当G 的每个面的次数均为3 证明:先证明该定理的必要性。其充分性在后续部分再证明 因为G为简单平面图,所以,G中无环和平行边。由定理5和定理6可知 G中无割点和桥。于是G中各面的次数大于或等于3,下面只需证明:G中各 面的次数不可能大于3 假设面R的次数deg(R)=s>3 在G中,若v1与v3不相邻,在R内加边1v3)不破坏平面性,这与G是极 大平面图矛盾,因此v1与v必相邻。由于R的存在,边(v1v3必在R外.类 似地,v2与v4也必相邻且边(2,V小必在R外这样,必产生(v1v)与(2,V 相交于R的外部,这与“G是平面图”相矛盾,故必有s=3,即G中不存在次 数大于3的面。 所以,G的每个面都由3条边所围,也就是说,各面的次数均为3
8 极大平面图 定理7. 设G为n(n ≥ 3)阶简单连通的平面图, G为极大平面图, 当且仅当G 的每个面的次数均为3。 证明: 先证明该定理的必要性。其充分性在后续部分再证明. 因为G为简单平面图, 所以, G中无环和平行边。由定理5和定理6可知, G中无割点和桥。于是G中各面的次数大于或等于3, 下面只需证明: G中各 面的次数不可能大于3。 假设面Ri的次数deg(Ri) = s > 3。 在G中, 若v1与v3不相邻, 在Ri内加边(v1, v3)不破坏平面性, 这与G是极 大平面图矛盾, 因此, v1与v3必相邻。由于Ri的存在,边(v1, v3)必在Ri外. 类 似地, v2与v4也必相邻, 且边(v2, v4)必在Ri外. 这样, 必产生(v1, v3)与(v2, v4) 相交于Ri的外部, 这与“G是平面图”相矛盾, 故必有s = 3, 即 G中不存在次 数大于3的面。 所以, G的每个面都由3条边所围, 也就是说, 各面的次数均为3