欧拉公式 定理8(欧拉公式)对于任意连通平面图G,有n-m+r=2.其中n,m 和分别为G的顶点数,边数和面数 证明:对边数m进行归纳 (1)m=0时,由于G为连通图,所以G只能是平凡图,结论显然 成立 (2)设m=k(k≥1)时,命题成立.当m=k+1时,分以下情况: 若G是树,则G是非平凡的,因此,G中至少有两个叶结点。设v 为叶结点,令G=GV,则G仍然是连通图,且G的边数m=m-1 k。由归纳假设可知n-m+r=2,其中n’,m,和r分别为G’的顶 点数,边数和面数.由n=n-1,r=r可得:nm+r=(n+1)-m+1)+r =n’-m’+r’=2 若G不是树,则G中含圈,设边e在G中某个圈上。令G”=G-e, 则G’仍连通,且m’=m-1=k。由归纳假设有n-m’+r=2。而n =n,r=r1,于是nm+r=n-(m+1)+(r+1)=n-m+r=2 1010 欧拉公式 证明: 对边数m进行归纳。 定理8(欧拉公式) 对于任意连通平面图G, 有n-m+r = 2. 其中 n, m 和r分别为G的顶点数, 边数和面数。 (1) m = 0时, 由于G为连通图, 所以 G只能是平凡图, 结论显然 成立。 (2) 设m = k(k ≥ 1)时, 命题成立. 当m = k+1时, 分以下情况: 若G是树, 则G是非平凡的, 因此, G中至少有两个叶结点。设v 为叶结点, 令G’ = G-v, 则G’仍然是连通图, 且G’的边数m’ = m-1 = k。由归纳假设可知 n’ – m’ + r’ = 2, 其中n’, m’,和r’分别为G’的顶 点数, 边数和面数. 由n’ = n-1, r’ = r可得: 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’ - m’ + r’ = 2。而n’ = n, r’ = r-1,于是 n-m+r = n’-(m’+1)+(r’+1) = n’-m’+r’ = 2