定义7.1.3设G为简单平面图,若在G的任意不相邻的顶点,v之间加边 后,所得之图成为非平面图,则称G是极大平面图。 易见K1,K2,K3,K4,K5-e都是极大平面图。 定义71.4若非平面图G任意删除一条边后,所得之图都是平面图,则称G为 极小非平面图。 容易证明下列定理 定理715极大平面图是连通的 定理71.6n阶(n≥3)极大平面图中没有割边和割点 §72欧拉公式 定理721(欧拉公式)设G是连通的平面图,n,m,r分别是其顶点数、边数和 面数,则 n-m+r=2 证明:对边数m作数学归纳法。 当m=0时,因G是连通图,所以G只能是平凡图,结论显然成立。 假设当m=k时,结论成立。下面证明m=k+1的情况。 若G是树,则G至少有两片树叶。设ν是G的一片树叶。令G′=G-ν,则 G仍是连通图,且G的边数m′=m-1=k,由归纳假设知,nm+r′=2,而n′=n-1 r'=r,于是 n-m+r=(m+1)-(m'+1)+r′=nm+r′=2。 若G不是树,则G中含有圈。设边e在G的某个圈上。令G′=G-e,则G′ 仍是连通图,且G的边数m′=m-1=k,由归纳假设知 n′m′+r′=2,而n′=n,r′=r-1, 于是 n-m+r=n'-(m′+1)+(r1)=n-m+r′=2 证毕 定理72(欧拉公式的推广形式)对于具有v(w≥1)个连通分支的平面图G,有 其中n,m,r分别是其顶点数、边数和面数。 证明:设G的连通分支分别为G1G2,…,G1,并设G1的顶点数、边数和面数 分别为n12m1F°由欧拉公式可知 22 定义 7.1.3 设 G 为简单平面图，若在 G 的任意不相邻的顶点 u, v 之间加边 uv 后，所得之图成为非平面图，则称 G 是极大平面图。 易见 K1, K2, K3, K4, K5– e 都是极大平面图。 定义 7.1.4 若非平面图 G 任意删除一条边后，所得之图都是平面图，则称 G 为 极小非平面图。 容易证明下列定理 定理 7.1.5 极大平面图是连通的。 定理 7.1.6 n 阶（ n ≥ 3）极大平面图中没有割边和割点。 §7.2 欧拉公式 定理 7.2.1（欧拉公式）设 G 是连通的平面图，n, m, r 分别是其顶点数、边数和 面数，则 n – m + r = 2。 证明：对边数 m 作数学归纳法。 当 m=0 时，因 G 是连通图，所以 G 只能是平凡图，结论显然成立。 假设当 m=k 时，结论成立。下面证明 m=k+1 的情况。 若 G 是树，则 G 至少有两片树叶。设 v 是 G 的一片树叶。令 G′ =G− v，则 G′ 仍是连通图, 且 G′ 的边数 m′ =m−1=k, 由归纳假设知, n′–m′ +r′ =2, 而 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′ 仍是连通图，且 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 。 证毕。 定理 7.2.2（欧拉公式的推广形式）对于具有 w(w ≥ 1)个连通分支的平面图 G, 有 n – m + r = w+1。 其中 n, m, r 分别是其顶点数、边数和面数。 证明：设 G 的连通分支分别为 G1, G2, …, Gw，并设 Gi 的顶点数、边数和面数 分别为 ni , mi , ri 。由欧拉公式可知