若G是树,则G是非平凡树,则G中至少有两片 树叶。设为其中一片树叶。令G′=G-1v}(从G中 删除结点v,而得到G,则G仍然是连通图。设 nm和r‘分别是G的结点数、边数和面数。则 n′=n-1,m′=m-1=k,r气r。于是n=n'+1 m=m'+1,r=r'。因为G是连通图且m=k,所以 G满足归纳假设的条件。由归纳假设知: m+r=2,所以 n-m+r(n+1)-(m’+1)+r'=n′m+r'=2
若G是树，则G是非平凡树，则G中至少有两片 树叶。设v为其中一片树叶。令G′=G-v(从G中 删除结点v，而得到G′)，则G′仍然是连通图。设 n′ 、m′和r′分别是G′的结点数、边数和面数。则 n′=n-1 ， m′=m-1=k ， r′ =r 。 于 是 n=n′+1 ， m=m′+1，r=r′ 。因为G′是连通图且m′=k，所以 G′满足归纳假设的条件。由归纳假设知： n′- m′+r′ =2，所以 n–m+r=( n′+1)–(m′ +1)+r′= n′-m′ +r′ =2
若G不是树,则G中含有回路。设边e在G的 某个回路上。令G=Ge(从G中删除边e,而得 到G),则G仍然是连通图。设n,m和r分别是 的结点数、边数和面数。则n'=n,m′=m-1=k, r′=r-1。于是n=n’,m=m+1,r=r+1。因为G 是连通图且m′=k,所以G满足归纳假设的条件 由归纳假设知:n’-m+r'=2,所以 n-m+rn-(m+1)+(r+1)=n-m+r′=2
若G不是树，则G中含有回路。设边e在G的 某个回路上。令G′=G-e(从G中删除边e，而得 到G′)，则G′仍然是连通图。设n′ ，m′和r′分别是 的结点数、边数和面数。则n′=n，m′=m-1=k， r′=r–1。于是n=n′ ，m=m′+1，r=r′+1。因为G′ 是连通图且m′=k，所以G′满足归纳假设的条件。 由归纳假设知：n′–m′＋r′=2，所以 n–m+r= n′–(m′+1)+(r′+1)= n′-m′+r′=2
欧拉公式成立是平面图的重要性质,条件是平面图的连通 性。欧拉公式还可以推广到非连通的平面图中。 定理:设G是平面图,有k个连通分支,n个结点,n条边, r个面,则公式n-mr=k+1成立 证明:设G的连通分支为G,n1m和r分别是G的结点 数、边数和面数,nrm2+r=2,÷=1,,k。 而∑m=m,∑n=m,由于每一个G有一个外部面,而(只 有一个外部面,所以c的面数=∑r+1,即∑=+k1。 所以2k=22=∑(-m1+户n1-∑m+∑r=mmr+k-1 整理后有nmt+r=k+1
欧拉公式成立是平面图的重要性质，条件是平面图的连通 性。欧拉公式还可以推广到非连通的平面图中。 定理：设G是平面图，有k个连通分支，n个结点，m条边， r个面，则公式n-m+r=k+1成立。 证明：设G的连通分支为Gi，ni、mi和ri分别是Gi的结点 数、边数和面数，ni -mi+ri=2，i=1,…,k。 而 =m， =n，由于每一个Gi有一个外部面，而G只 有一个外部面，所以G的面数r= -k+1，即 =r+k-1。 所以2k= = = – ＋ =n-m+r+k-1 整理后有n-m+r=k+1。 = k i mi 1 = k i ni 1 = k i i r 1 = k i i r 1 = k i 1 2 ( ) 1 i i k i i n − m + r = = k i i n 1 = k i mi 1 = k i i r 1
定理:设G是连通的平面图,且每个面的次 数至少为(I≥3),则 1-2 其中,n为G中的顶点数,m为边数。 例:如右所示的平面图 0 8n=6l>3 2 (n-2) l-2 3 8≤12(取=3或4)
定理 ：设G是连通的平面图，且每个面的次 数至少为l ( l ≥3），则 其中, n为G中的顶点数, m为边数。 例：如右所示的平面图 m=8 n=6 l ≥3 R3 R1 R2 R0 m≤ ( n – 2 ) l-2 l ∴ 8 ≤12 ( 取l=3或4 ) ( 2) 2 l m n l − −
定理设G是简单平面图,有n(m≥3)个结点,m条边 H3-6 证明设G有(≥1)个连通分支。 若G为树或森林,则 nn-s≤n+6-6=n+3+3-6≤n+n+n-6=3n-6。 即n3n6 若G不是树,也不是森林,则G必含有回路。又因为 G是简单平面图,所以其中的回路的长度均大于等于3,因 k 2 而各面次数23,又k-2-1+k2,当k=3时,达到最大 值3,因此: k(n-s-1)≤3(ms1)3(n1-1)≤3n-6
定理 设G是简单平面图，有n(n≥3)个结点，m条边，则 m≤3n-6 证明:设G有s (s≥1)个连通分支。 若G为树或森林，则 m=n-s≤n=n+6-6=n+3+3-6≤n+n+n-6=3n–6。 即 m≤3n–6 若G不是树，也不是森林，则G中必含有回路。又因为 G是简单平面图，所以其中的回路的长度均大于等于3，因 而各面次数k≥3，又 =1+ ，当 k=3 时，达到最大 值3，因此： m≤ ≤ 3(n-s-1)≤3(n-1-1)≤3n-6。 k − 2 k 2 2 k − ( 1) 2 − − − n s k k