17.2欧抗公式 欧拉公式相关定理 1、欧拉公式 定理78对于任意的连通的平面图G,有 n-nt+产=2 其中,n、mr别为G的顶点数、边数和面数 证明 对边数m作归纳法。 (1)m=0时,由于G为连通图,所以G只能是由一个孤立顶 点组成的平凡图,即n=1,mF=0,r=1,结论显然成立。 (2)m=1时,由于G为连通图,所以m=2,m=1,p1,结论 显然成立
17.2 欧拉公式 一、欧拉公式相关定理 1、 欧拉公式 定理17.8 对于任意的连通的平面图G，有 n-m+r=2 其中，n、m、r分别为G的顶点数、边数和面数。 证明 对边数m作归纳法。 (1) m＝0时，由于G为连通图，所以G只能是由一个孤立顶 点组成的平凡图，即n=1，m=0，r=1，结论显然成立。 (2) m＝1时，由于G为连通图，所以n=2，m=1，r=1，结论 显然成立
(3)设m=k(k1)时成立,当m=k+1时,对G进行如下讨论。 口若G是树,则G是非平凡的,因而G中至少有两片树叶。 设v为树叶,令G=G-ν,则G仍然是连通图,且G"的边数 m'=m-1=k, n=n-1, r=r 由假设可知n'-m+r'=2,式中n',m,r分别为G"的顶点数, 边数和面数。 于是n-m+r=(n+1)-(m+1)+r=n-m+r'=2 口若G不是树,则G中含圈。 设边e在G中某个圈上,令G=G-e,则G仍连通且m=m-1=k n'=n,r'=r-1 由假设有m-m+r'=2。 于是n-m+r=n'-(m+1)-(r+1)=n-m+r'=2
(3)设m＝k(k≥1)时成立，当m＝k+1时，对G进行如下讨论。 ❑ 若G是树，则G是非平凡的，因而G中至少有两片树叶。 设v为树叶，令G'=G-v，则G'仍然是连通图，且G'的边数 m'=m-1=k，n'=n-1，r'=r。 由假设可知n'-m'+r'=2，式中n' ，m' ，r'分别为G'的顶点数， 边数和面数。 于是n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2 ❑ 若G不是树，则G中含圈。 设边e在G中某个圈上，令G'=G-e，则G'仍连通且m'=m-1=k ， n'=n，r'=r-1。 由假设有 n'-m'+r'=2。 于是 n-m+r=n'-(m'+1)-(r'+1)=n'-m'+r'=2
定理。9对于具有k(22)个连通分支的平面图G,有 n-mtr=k+1 其中n,m,r分别为G的顶点数,边数和面数。 证明 边数、面数分别为m2,并设G的顶点数 设G的连通分支分别为G1、G2 由欧拉公式可知:n-m+r;=2,i=1,2,∴,k (17.1) 易知,m=∑m,n=∑n i=1 由于每个G有一个外部面,而G只有一个外部面,所以G的面数 k+1 于是,对(171)的两边同时求和得 2k=∑(n-m+1)=∑n-∑m+∑=n-m+r+k 经整理得n-m+r=k+1
定理17.9 对于具有k(k≥2)个连通分支的平面图G，有 n-m+r = k+1 其中n，m，r分别为G的顶点数，边数和面数。 证明 设G的连通分支分别为G1、G2、…、Gk，并设Gi的顶点数、 边数、面数分别为ni、mi、ri、i=1，2，…，k。 由欧拉公式可知: ni -mi+ri = 2，i=1，2，…，k (17.1) 易知， 1 1 k k i i i i m m n n = = = = ， 由于每个Gi有一个外部面，而G只有一个外部面，所以G的面数 1 1 k i i r r k = = − + 于是，对(17.1)的两边同时求和得 1 1 1 1 2 ( ) 1 k k k k i i i i i i i i i i k n m r n m r n m r k = = = = = − + = − + = − + + − 经整理得 n-m+r = k+1
与欧拉公式有关的定理 定理70设G为连通的平面图,且每个面的次数至少为 取(3),则G的边数与顶点数有如下关系: 证明 由定理174(面的次数之和等于边数的2倍)及欧拉公式得 2m=∑deg(R)≥1,r=l 解得m (n-2)
2、 与欧拉公式有关的定理 定理17.10 设G为连通的平面图，且每个面的次数至少为 l(l 3)，则G的边数与顶点数有如下关系： 由定理17.4（面的次数之和等于边数的2倍）及欧拉公式得 ( 2) 2 l m n l − − 证明 1 2 deg( ) (2 ) r i i m R l r l m n = = = + − 解得 ( 2) 2 l m n l − −
组论K5,K3不是平面图。 证明 口若K是平面图,由于K中无环和平行边,所以每个面的次数 均大于或等于忪3,由定理1710可知边数10应满足 10≤(3/(3-2)(5-2)=9 这是个矛盾,所以K不是平面图。 口若K32是平面图,由于K32中最短圈的长度为上4,于是边数9 应满足 9≤(4(4-2)(6-2)=8 这又是矛盾的,所以K2也不是平面图
推论 K5 , K3,3不是平面图。 证明 ❑若K5是平面图，由于K5中无环和平行边，所以每个面的次数 均大于或等于l≥3，由定理17.10可知边数10应满足 10≤(3/(3-2))(5-2) = 9 这是个矛盾，所以K5不是平面图。 ❑若K3,3是平面图，由于K3,3中最短圈的长度为l≥4，于是边数9 应满足 9≤ (4/(4-2))(6-2) = 8 这又是矛盾的，所以K3,3也不是平面图