◆对于简单图来讲,它的每个内部面至少 要由三条边围成,每条边最多为两个面 的边界。 ◆定理6.1:若连通平面图G有n个顶点,e条 边和个面,则ne+2-称为欧拉公式 ◆证明:对边数进行归纳证明:对于一条边 的连通平面图, 第一个n=2,f=1,e=1,n-e+f=2,成立 第二个n=1,f=2,e=1,n-e+f=2成立
对于简单图来讲，它的每个内部面至少 要由三条边围成，每条边最多为两个面 的边界。 定理6.1：若连通平面图G有n个顶点,e条 边和f个面,则n-e+f=2---称为欧拉公式 证明：对边数进行归纳证明: 对于一条边 的连通平面图, 第一个n=2,f=1,e=1,n-e+f=2,成立 第二个n=1,f=2,e=1,n-e+f=2,成立
◆假设对于一切m-1条边的连通平面图,欧拉 公式均成立。现考察m条边的连通平面图。 (1)若G有一个度数为1的顶点,则删去该顶 点及其关联边,便得到一个连通平面图G 删去度数为1的顶点不影响连通 性。而且度数为1的顶点不在回 路上,因此不会增加和减少回 路数。因此面数不变
假设对于一切m-1条边的连通平面图, 欧拉 公式均成立。现考察m条边的连通平面图。 (1)若G有一个度数为1的顶点, 则删去该顶 点及其关联边, 便得到一个连通平面图G'。 删去度数为1的顶点不影响连通 性。而且度数为1的顶点不在回 路上，因此不会增加和减少回 路数。因此面数不变
Q'名没有度数为顶点则删去同 上的一条边不影响连通性,因此得到 个连通平面图G
(2)若G中没有度数为1的顶点,则删去一个 有界面边界上的任一条边,因为删去回路 上的一条边不影响连通性，因此得到一 个连通平面图G
◆对于平面图,嵌如平面的画法可以有多 种,但不管怎样,面数总是相等的。必 须强调的是:欧拉公式只适用于连通平 面图, ◆即任何一个连通平面图一定满足欧拉公 式, 不满足欧拉公式的连通图一定不是平面 ◆但是面数确定是比较困难的
对于平面图，嵌如平面的画法可以有多 种，但不管怎样，面数总是相等的。必 须强调的是：欧拉公式只适用于连通平 面图， 即任何一个连通平面图一定满足欧拉公 式， 不满足欧拉公式的连通图一定不是平面 图。 但是面数确定是比较困难的
◆推论61:若G是n3的平面简单图,则e≤3n-6 证明显然只要对连通平面简单图证明即可。 c设G是n3的连通平面简单图G的每个面由 条或更多条边围成因此边的总数s大于或等于 3f这里边的总数包括重复计算在内) 即s≥3f s=4+3+3+6=16 另一方面,因为每条边至多是两个 面的公共边,也就是说每条边至多 被计算两次,即s2e
推论 6.1：若G是n3的平面简单图, 则e3n-6。 证明:显然只要对连通平面简单图证明即可。 设G 是n3的连通平面简单图,G的每个面由三 条或更多条边围成,因此边的总数s大于或等于 3f(这里边的总数包括重复计算在内)。 即s3f s=4+3+3+6=16 另一方面, 因为每条边至多是两个 面的公共边, 也就是说每条边至多 被计算两次,即s2e