超详细证明题总结

基本证明

设 $d_1,d_2,\cdots ,d_n$$d_1,d_2,\cdots,d_n$ 是 $n$$n$ 个不同的正整数。求证：序列 $\pi =(d_1,d_2,\cdots ,d_n)$$\pi=(d_1,d_2,\cdots,d_n)$ 不能是简单图的度序列

证明：一个简单图 $G$$G$ 的 $n$$n$ 个点的度不能互不相同

所以显然，序列 $\pi =(d_1,d_2,\cdots ,d_n)$$\pi=(d_1,d_2,\cdots,d_n)$ 不能是简单图的度序列

用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同

证明：以人为顶点，如果两个人相识，对应的顶点之间连一条边，得到的图记为 $G$$G$

显然图 $G$$G$ 是简单图

当一个人的朋友数等于他在图中对应顶点的度数

因为简单图中一定存在度数相等的顶点，所以在任何一个人群中至少有两个人认识的朋友数相同

设 $G$$G$ 为 $n$$n$ 阶简单无向图，$n>2$$n > 2$ 且 $n$$n$ 为奇数，$G$$G$ 与 $G$$G$ 的补图 $\bar{G}$$\overline G$ 中度数为奇数的顶点个数是否相等？

解：由补图定义知，任意点 $v$$v$ 在图 $G$$G$ 及其补图 $\bar{G}$$\overline G$ 中的度数之和为 $n-1$$n-1$，即：$d_G(v)+d_{\bar{G}}(v)=n-1$$d_G(v)+d_{\overline G}(v)=n-1$

因此，若 $G$$G$ 中有 $b_i$$b_i$ 个度为奇数的顶点，其度数为 $d_i$$d_i$，则这 $b_i$$b_i$ 个顶点在 $\bar{G}$$\overline G$ 中的度数为 $n-1-d_i$$n-1-d_i$

因为 $n$$n$ 为奇数，故 $n-1$$n-1$ 为偶数，所以 $n-1-d_i$$n-1-d_i$ 为奇数

综上所述，$G$$G$ 与其补图中度数为奇数的顶点个数相等

设 $\mathrm{\Delta }$$\Delta$ 和 $\delta$$\delta$ 分别是 $(n,m)$$(n,m)$ 图 $G$$G$ 的最大度与最小度。求证：$\delta \le \frac{2m}{n}\le \mathrm{\Delta }$$\delta \le \frac{2m}{n} \le \Delta$

证明：根据握手定理，有：$n\delta \le 2m\le n\mathrm{\Delta }$$n\delta \le 2m \le n\Delta$

所以：$\delta \le \frac{2m}{n}\le \mathrm{\Delta }$$\delta \le \frac{2m}{n} \le \Delta$

求证：任意图中奇度点个数一定为偶数

证明：若不然，假设图中奇度点个数为奇数

显然，图中所有顶点度数之和也一定为奇数，这与握手定理矛盾！

所以任意图中奇度点个数一定为偶数

求证：若 $G$$G$ 恰有两个奇度点 $u$$u$ 和 $v$$v$，则 $u$$u$ 与 $v$$v$ 必连通

证明：若不然，假设 $u$$u$ 和 $v$$v$ 不连通，且连通分支 $F_1$$F_1$ 包含 $u$$u$

显然连通分支 $F_1$$F_1$ 中除了点 $u$$u$ 的度数为奇数外，其余点度数均为偶数

所以 $F_1$$F_1$ 中所有顶点度数之和也一定为奇数，与握手定理矛盾！！

故：$u$$u$ 与 $v$$v$ 必连通

树相关证明

求证：一棵非平凡树至少有两片树叶

证明： 若不然，假设每棵非平凡树至多有一片树叶

在树 $T$$T$ 中找一条最长的路，假设为 $P$$P$，且依次经过 $v_1,v_2,\cdots ,v_k$$v_1,v_2,\cdots,v_k$

因为非平凡树至多只有一片树叶，那么 $v_1$$v_1$ 或 $v_k$$v_k$ 一定至少存在两个邻接顶点

假设 $v_1$$v_1$ 有两个邻接顶点，所以除了 $v_2$$v_2$ 一定还存在另外一个邻接顶点

假设 $v_1$$v_1$ 另外一个邻接顶点为 $u$$u$，那么一定有 $u\in P$$u \in P$

所以路 $P$$P$ 上一定存在圈 $v_1{v}_2\cdots u{v}_1$$v_1v_2\cdots uv_1$

显然和树的定义矛盾！所以一棵非平凡树至少有两片树叶

求证：一棵非平凡树最多只有一个完美匹配

证明：若不然，设 $M_1$$M_1$ 与 $M_2$$M_2$ 是树 $T$$T$ 的两个不同的完美匹配，那么 $M_1\mathrm{\Delta }{M}_2\ne \varnothing$$M_1 \Delta M_2 \ne \varnothing$

容易知道：$T[M_1\mathrm{\Delta }{M}_2]$$T[M_1 \Delta M_2]$ 的每个顶点度数为 2，即它存在圈，于是推出 $T$$T$ 中有圈，矛盾！

设 $T$$T$ 是完全 $m$$m$ 元树，$i$$i$ 是分支点数，$t$$t$ 是树叶数。证明：$(m-1)i=t-1$$(m-1)i=t-1$

证明：出度 = 入度 = 边数

所以有：$mi=t+i-1$$mi=t+i-1$

故：$(m-1)i=t-1$$(m-1)i=t-1$

设 $\tau (G)$$\tau(G)$ 表示图 $G$$G$ 的生成树的棵数。求证：对图 $G$$G$ 的任意一条边 $e$$e$ 来说，有 $\tau (G)=\tau (G-e)+\tau (G\cdot e)$$\tau(G)=\tau(G-e)+\tau(G\cdot e)$

证明：由于 $G$$G$ 的每一棵不包含 $e$$e$ 的生成树也是 $G-e$$G-e$ 的生成树

由此推知，$\tau (G-e)$$\tau (G-e)$ 就是 $G$$G$ 不包含 $e$$e$ 的生成树的个数

类似的，$\tau (G\cdot e)$$\tau(G\cdot e)$ 就是 $G$$G$ 的包含 $e$$e$ 的生成树的个数

• 理解：因为收缩了边 $e$$e$，故当经过收缩顶点时，还原到原图中，即经过了边 $e$$e$

正整数序列 $d_1,d_2,\cdots ,d_n$$d_1,d_2,\cdots,d_n$ 是一棵树的度序列的充分必要条件是 $\sum _{i=1}^n{d}_i=2(n-1)$$\sum\limits^n_{i=1}d_i=2(n-1)$

证明：

必要性：根据握手定理显然成立

充分性：（很长很长很长很长。。。。。）祈求不要出吧！！！

偶图

证明：若 $k$$k$ 正则二部图具有而分类 $V=V_1\cup V_2$$V = V_1 \cup V_2$，则 $|V_1|=|V_2|$$|V_1|=|V_2|$

证明：对于二部图来说，因为边是建立在顶点集的二部划分之间的，所以边数即等于 $V_1$$V_1$ 中的顶点的度数之和，也等于 $V_2$$V_2$ 中顶点的度数之和

故有：$k\times |V_1|=|E|=k\times |V_2|$$k \times |V_1| = |E| = k \times |V_2|$

所以：$|V_1|=|V_2|$$|V_1|=|V_2|$

偶图 + 完美匹配

共有 $n$$n$ 为男士和 $n$$n$ 位女士参加一次舞会，已知每位男士至少认识两位女士，而每位女士至多认识两位男士。能否将男士和女士分配为 $n$$n$ 对，使得每队中的男士和女士彼此相识？

解：以人为顶点，相识的异性之间连一条边，得到图记为 $G$$G$

图 $G$$G$ 显然是一个二部图

设男士为集合 $X$$X$，女士为集合 $Y$$Y$，构成二部图 $(X,Y)$$(X,Y)$

显然：

$$\begin{array}{c}\{\begin{array}{c}\mathrm{\forall }x\in X,\delta (x)\ge 2\\ \mathrm{\forall }y\in Y,\delta (y)\le 2\end{array}\Rightarrow \{\begin{array}{c}\sum _{x\in V(X)}d(x)\ge 2n\\ \sum _{y\in V(Y)}d(y)\le 2n\end{array}\end{array}$$

根据二部图的性质得：$\sum _{x\in V(X)}d(x)=\sum _{y\in V(Y)}d(y)$$\sum\limits_{x\in V(X)}d(x) = \sum\limits_{y\in V(Y)}d(y)$

故：$\sum _{x\in V(X)}d(x)=\sum _{y\in V(Y)}d(y)=2n$$\sum\limits_{x\in V(X)}d(x) = \sum\limits_{y\in V(Y)}d(y)=2n$

故：$\mathrm{\forall }x\in X,\mathrm{\forall }y\in Y,d(x)=d(y)=2$$\forall x \in X, \ \forall y \in Y, \ d(x)=d(y)=2$

故 $(X,Y)$$(X,Y)$ 为二正则偶图，存在完美匹配

所以能将男士和女士分配为 $n$$n$ 对，使得每队中的男士和女士彼此相识

割边

求证：若连通图 $G$$G$ 的每个顶点的度数均为偶数，则 $G$$G$ 没有割边

证明：若不然，假设 $e=uv$$e=uv$ 为 $G$$G$ 的割边，$G-e$$G-e$ 的两个连通分支为 $F_1$$F_1$ 和 $F_2$$F_2$

不妨考虑连通分支 $F_1$$F_1$，设分支 $F_1$$F_1$ 包含 $u$$u$

显然分支 $F_1$$F_1$ 中除了点 $u$$u$ 的度数为奇数外，其余点度数均为偶数

所以 $F_1$$F_1$ 中所有顶点度数之和也一定为奇数，与握手定理矛盾！！

故：$G$$G$ 没有割边

证明：若 $k>1$$k>1$，则 $k$$k$ 正则偶图 $G$$G$ 没有割边

证明：若不然，假设 $e=uv$$e=uv$ 为 $G$$G$ 的割边

假设 $G_1$$G_1$ 是 $G-e$$G-e$ 包含点 $u$$u$ 的连通分支，显然 $G_1$$G_1$ 中除了点 $u$$u$ 的度数为 $k-1$$k-1$ 外其他点的度数均为 $k$$k$

显然 $G_1$$G_1$ 也为偶图，设其二部划分为 $S$$S$ 和 $T$$T$，且 $s=|S|$$s = |S|$，$t=|T|$$t=|T|$

不妨假设 $S$$S$ 包含顶点 $u$$u$，则有：$ks-1=|E(G_1)|=kt$$ks - 1 = |E(G_1)| = kt$

但是因 $k>1$$k>1$，所以上式不成立。因此 $e$$e$ 一定不是割边

边连通

证明：设简单图 $G$$G$ 是 $k$$k$ 边连通的，$E^{{}^{\prime }}$$E^{'}$ 是 $G$$G$ 的某 $k$$k$ 条边构成的集合，则 $\omega (G-E^{{}^{\prime }})\le 2$$\omega(G-E^{'}) \le 2$

证明：因为简单图 $G$$G$ 是 $k$$k$ 边连通的，所以 $\lambda (G)\ge k$$\lambda(G) \ge k$；同时 $|E^{{}^{\prime }}|=k$$|E^{'}| = k$

如果 $E^{{}^{\prime }}$$E^{'}$ 是边割，那么 $E^{{}^{\prime }}$$E^{'}$ 一定是最小边割，所以 $\omega (G-E^{{}^{\prime }})=2$$\omega(G-E^{'}) = 2$

如果 $E^{{}^{\prime }}$$E^{'}$ 不是边割，那么删去 $E^{{}^{\prime }}$$E^{'}$ 中的边后不会破坏图的连通性，所以 $\omega (G-E^{{}^{\prime }})=1$$\omega(G-E^{'}) = 1$

综上所述：$E^{{}^{\prime }}$$E^{'}$ 是 $G$$G$ 的某 $k$$k$ 条边构成的集合，则 $\omega (G-E^{{}^{\prime }})\le 2$$\omega(G-E^{'}) \le 2$

最小度

证明：若 $n$$n$ 阶简单图 $G$$G$ 满足 $\delta (G)\ge n-2$$\delta(G) \ge n - 2$，则 $\kappa (G)=\delta (G)$$\kappa(G)=\delta(G)$

证明：显然：$n-2\le \delta (G)\le n-1$$n - 2 \le \delta(G) \le n - 1$

如果 $\delta (G)=n-1$$\delta(G) = n - 1$，则图 $G$$G$ 一定是完全图 $K_n$$K_n$，此时图 $G$$G$ 的点连通度和最小度均为 $n-1$$n - 1$

如果 $\delta (G)=n-2$$\delta(G) = n - 2$，只需证明：「任意删除 $n-3$$n-3$ 个顶点，不会破坏图的连通性」即可

任意删除 $n-3$$n-3$ 个顶点，那么只留下了 $3$$3$ 个顶点，假设为 $x,y,z$$x, y, z$

由于 $\delta (G)=n-2$$\delta(G) = n - 2$，故 $x,y,z$$x,y,z$ 中一定有一个邻接顶点留下

假设 $y$$y$ 是 $x$$x$ 的邻接顶点，如果 $x$$x$ 不是 $z$$z$ 的邻接，那么 $y$$y$ 一定与 $z$$z$ 相邻，所以 $x,y,z$$x,y,z$ 连通

假设 $y$$y$ 不是 $x$$x$ 的邻接顶点，那么 $z$$z$ 一定与 $x$$x$ 和 $y$$y$ 相邻，所以 $x,y,z$$x,y,z$ 连通

得证：「任意删除 $n-3$$n-3$ 个顶点，不会破坏图的连通性」所以 $\kappa (G)\ge n-2$$\kappa(G) \ge n-2$

又因为 $n-2\le \kappa (G)\le \delta (G)=n-2$$n-2 \le \kappa(G) \le \delta(G) = n - 2$，所以 $\kappa (G)=\delta (G)$$\kappa(G)=\delta(G)$

证明：如果一个图 $G$$G$ 满足：$\delta (G)\ge 2$$\delta(G)\ge 2$ ，那么一定有圈存在

在图 $G$$G$ 中找一条最长的路，假设为 $P$$P$，且依次经过 $v_1,v_2,\cdots ,v_k$$v_1,v_2,\cdots,v_k$

因为 $d(v_1)\ge 2$$d(v_1) \ge 2$，那么 $v_1$$v_1$ 一定有两个邻接顶点，所以除了 $v_2$$v_2$ 一定还存在另外一个邻接顶点

假设 $v_1$$v_1$ 另外一个邻接顶点为 $u$$u$，那么一定有 $u\in P$$u \in P$

所以路 $P$$P$ 上一定存在圈 $v_1{v}_2\cdots u{v}_1$$v_1v_2\cdots uv_1$

哈密尔顿图相关

证明：若 $n$$n$ 阶简单图 $G$$G$ 满足 $\delta (G)\ge (n-1)/2$$\delta(G) \ge (n-1)/2$，则 $G$$G$ 包含哈密尔顿路

证明：在图 $G$$G$ 的基础上添加一个顶点 $v$$v$，让点 $v$$v$ 与图 $G$$G$ 的每个顶点都相连，得到新图，记为 $K$$K$

那么，在 $H$$H$ 中，一定存在 $\delta (K)\ge (n+1)/2$$\delta(K) \ge (n+1)/2$

根据 Dirac 定理，图 $K$$K$ 一定是哈密尔顿图

从图 $K$$K$ 的哈密尔顿圈上去掉新添加的顶点 $v$$v$，就变成了原图 $G$$G$ 的一条哈密尔顿路

证明：对于一般的 $m$$m$ 和 $n$$n$，其中 $1\le m\le \frac{n}{2}$$1\le m \le \frac{n}{2}$。证明：$C_{m,n}$$C_{m,n}$ 图不是哈密尔顿图

证明：取 $S=V(K_m)$$S=V(K_m)$，则 $\omega (G-S)=m+1>|S|=m$$\omega(G-S)=m+1>|S|=m$，所以，由 $H$$H$ 图的性质知，$G$$G$ 不是 $H$$H$ 图

求证：若 $G$$G$ 是 $n\ge 3$$n\ge 3$ 的非哈密尔顿简单图，则 $G$$G$ 度弱于某个 $C_{m,n}$$C_{m,n}$ 图

证明：设 $G$$G$ 是度序列为 $(d_1,d_2,\cdots ,d_n)$$(d_1,d_2,\cdots,d_n)$ 的非 $H$$H$ 简单图，且 $d_1\le d_2\le \cdots d_n$$d_1 \le d_2 \le \cdots d_n$

由度序列判定法：存在 $m<n/2$$m<n/2$，使得 $d_m\le m$$d_m\le m$，且 $d_{n-m}<n-m$$d_{n-m} < n-m$

于是，$G$$G$ 的度序列必弱于如下序列：

$$\stackrel{m}{\overbrace{m,m,\cdots ,m}},\stackrel{n-2m}{\overbrace{n-m-1,n-m-1,\cdots ,n-m-1}},\stackrel{m}{\overbrace{n-1,n-1,\cdots ,n-1}}$$

而上面序列正好是图 $C_{m,n}$$C_{m,n}$ 的度序列

因子分解

证明：若 $k>0$$k>0$，则 $k$$k$ 正则偶图可 1-因子分解

证明：因正则偶图存在完美匹配，即 1-因子，从不断减去完美匹配的方式就可得到正则偶图的 1-因子分解

证明：完全图 $K_{6n-2}$$K_{6n-2}$ 可以 3-因子分解

证明：设 $\mathrm{\forall }v\in V(K_{6n-2})$$\forall v \in V(K_{6n-2})$，显然：$d(v)=6n-3$$d(v)=6n-3$，即：完全图 $K_{6n-2}$$K_{6n-2}$ 是 $6n-3$$6n-3$ 正则图

所以 $K_{6n-2}$$K_{6n-2}$ 可以分解为 $6n-3$$6n-3$ 个边不重的 1-因子的并

将每 $3$$3$ 个 1-因子合并成一个 3-因子，故恰好有 $2n-1$$2n-1$ 个 3-因子

所以完全图 $K_{6n-2}$$K_{6n-2}$ 可以 3-因子分解

求证：对于 $n\ge 1$$n \ge 1$，完全图 $K_{4n+1}$$K_{4n+1}$ 是 4-可因子分解的

证明：阶数为奇数，显然可以 2-因子分解

可以分解成 $2n$$2n$ 个边不重的 2-因子的并

将每 $2$$2$ 个 2-因子合并成一个 4-因子，故恰好有 $n$$n$ 个 4-因子

所以完全图 $K_{4n+1}$$K_{4n+1}$ 可以 4-因子分解

若 $n$$n$ 为偶数，且简单图 $G$$G$ 满足：$\delta \ge \frac{n}{2}+1$$\delta\ge \frac{n}{2}+1$。求证：$G$$G$ 中有 3 因子

证明：因 $\delta (G)\ge \frac{n}{2}+1$$\delta(G) \ge \frac{n}{2} + 1$，由 Dirac 定理 得：$n$$n$ 阶图 $G$$G$ 有 $H$$H$ 圈 $C$$C$

又因 $n$$n$ 为偶数，所以 $C$$C$ 为偶圈

于是由 $C$$C$ 可得到 $G$$G$ 的两个 1 因子，设其中一个为 $F_1$$F_1$

考虑 $G_1=G-F_1$$G_1=G-F_1$，则 $\delta (G_1)\ge \frac{n}{2}$$\delta(G_1)\ge \frac{n}{2}$。于是 $G_1$$G_1$ 中有 $H$$H$ 圈 $C_1$$C_1$

作 $H=C_1\bigcup F_1$$H=C_1 \bigcup F_1$。显然 $H$$H$ 是 $G$$G$ 的一个 3-因子

求证：设 $G$$G$ 是 $n$$n$ 阶简单图 $(m\ge 4)$$(m \ge 4)$，$n$$n$ 为偶数，且最小度 $\delta \ge \frac{n}{2}+3$$\delta\ge \frac{n}{2}+3$，则图 $G$$G$ 中存在 5 因子

同上！！！

最小覆盖 -> 最大匹配

假定 $G$$G$ 是具有 $m$$m$ 条边的简单二部图，顶点的最大度为 $\mathrm{\Delta }$$\Delta$。证明：$G$$G$ 包含一个至少有 $m/\mathrm{\Delta }$$m/\Delta$ 条边的匹配

证明：因为顶点的最大度为 $\mathrm{\Delta }$$\Delta$，所以一个顶点最多可以覆盖 $\mathrm{\Delta }$$\Delta$ 条边

由于图 $G$$G$ 有 $m$$m$ 条边，所以最少需要 $m/\mathrm{\Delta }$$m/\Delta$ 个顶点才能覆盖所有的边

所以最小覆盖中的点数一定大于等于 $m/\mathrm{\Delta }$$m/\Delta$

根据 König 定理，最大匹配中至少有 $m/\mathrm{\Delta }$$m/\Delta$ 条边

矩阵中一行或一列称为矩阵的一条线，利用哥尼定理证明：布尔矩阵中，包含了所有 1 的最少数目，等于具有性质「任意两个 1 都不在同一条线上的 1 的数目」（注：哥尼定理：在偶图中，最大匹配包含的边数等于最小点覆盖包含的顶点数）

证明：设布尔阵是 $n$$n$ 行 $m$$m$ 列矩阵，每行每列分别用一个点表示，$X$$X$ 表示行点集合，$Y$$Y$ 表示列点集合，两点连线，当且仅当该行该列元为 1

于是，包含了所有「1」的线的最少数目对应偶图中的最小点覆盖数；而具有性质「任意两个 1 都不在同一条线上的 1 的最大数目」对应偶图的最大匹配包含的边数。由哥尼定理，命题得到证明

有一个街区如下图所示，其中所有街道都是直线段。为了在巷战中能控制所有的街道，需要在街口处修筑碉堡，其中一个碉堡可以控制与其关联的所有街道。问最少需要多少个碉堡？并给出一种具体修建的位置。(用图论方法解答)

定理 61：设 $M$$M$ 是匹配，$K$$K$ 的覆盖，若 $|M|=|K|$$|M|=|K|$，则 $M$$M$ 是最大匹配，且 $K$$K$ 是最小覆盖

证明：显然，上图是二部图

可以很容易找到一个匹配 $\{24,35,68,79\}$$\{24, 35, 68, 79\}$，大小为 $4$$4$

也可以很容易找到一个覆盖 $\{2,5,6,9\}$$\{2,5,6,9\}$，大小为 $4$$4$

所以该覆盖是最小覆盖

故原问题最少需要 $4$$4$ 个碉堡，分别修在 $\{2,5,6,9\}$$\{2,5,6,9\}$ 处即可

平面图

求证：设 $G$$G$ 是 $n$$n$ 阶的具有 $m$$m$ 条边的简单连通平面图，则：$m\le 3n-6$$m \le 3n - 6$

证明：由于 $G$$G$ 是 $n$$n$ 阶的具有 $m$$m$ 条边的简单连通平面图，所以对于每个面 $f$$f$ 有：$deg(f)\ge 3$$deg(f)\ge3$

由 $\sum _{f\in \mathrm{\Phi }}deg(f)=2m$$\sum\limits_{f \in \Phi}deg(f) = 2m$ 可以得到：$\phi \le \frac{2}{3}m$$\varphi \le \frac{2}{3}m$

由连通平面图的欧拉公式得：$n-m+\phi =2$$n-m+\varphi=2$

将 $\phi \le \frac{2}{3}m$$\varphi \le \frac{2}{3}m$ 代入得：$m\le 3n-6$$m \le 3n - 6$

求证：在 $n$$n$ 阶简单平面图 $G$$G$ 中有 $\phi \le 2n-4$$\varphi \le 2n-4$，这里 $\phi$$\varphi$ 是 $G$$G$ 的面数

证明：由连通平面图的欧拉公式得：$n-m+\phi =2$$n-m+\varphi=2$

根据简单连通平面图有：$m\le 3n-6$$m \le 3n - 6$

整理得：$\phi \le 2n-4$$\varphi \le 2n-4$

求证：在 $n$$n$ 阶简单平面图 $G$$G$ 中有 $\delta (G)\le 5$$\delta(G) \le 5$

证明：若不然，假设 $\delta (G)>5$$\delta(G) > 5$

根据握手定理得：$2m>n\delta (G)>6n$$2m > n\delta(G) > 6n$；进一步有：$m>3n>3n-6$$m > 3n > 3n - 6$

这显然与 $m\le 3n-6$$m \le 3n - 6$ 矛盾！

所以在 $n$$n$ 阶简单平面图 $G$$G$ 中有 $\delta (G)\le 5$$\delta(G) \le 5$

求证：若 $G$$G$ 是连通平面图，且所有顶点度数不小于 3，则 $G$$G$ 至少有一个面 $f$$f$，使得 $deg(f)\le 5$$deg(f) \le 5$

证明：若不然，假设对于 $G$$G$ 的所有面 $f$$f$，均有 $deg(f)>5$$deg(f) > 5$

由 $\sum _{f\in \mathrm{\Phi }}deg(f)=2m$$\sum\limits_{f \in \Phi}deg(f) = 2m$ 可以得到：$2m\ge 6\phi$$2m \ge 6\varphi$

由连通平面图的欧拉公式得：$n-m+\phi =2$$n-m+\varphi=2$

整理得：$2m\le 3n-6<3n$$2m \le 3n - 6 < 3n$

根据「所有顶点度数不小于 3」和握手定理得：$2m\ge 3n$$2m \ge 3n$

显然矛盾！！所以 $G$$G$ 至少有一个面 $f$$f$，使得 $deg(f)\le 5$$deg(f) \le 5$

设 $G$$G$ 是具有 $n$$n$ 个顶点，$m$$m$ 条边，$p(p\ge 2)$$p \ (p \ge 2)$ 个连通分支的平面图，$G$$G$ 的每个面至少由 $k(k\ge 3)$$k \ (k \ge 3)$ 条边所围成，则 $m\le \frac{k(n-p-1)}{k-2}$$m \le \frac{k(n-p-1)}{k-2}$

证明：由连通平面图的欧拉公式得：$n-m+\phi =2$$n-m+\varphi=2$

根据握手定理得：$2m\ge \phi k$$2m \ge \varphi k$

整理得：$m\le n-p-1+\frac{2m}{k}$$m \le n-p-1+\frac{2m}{k}$

化简得：$m\le \frac{k(n-p-1)}{k-2}$$m \le \frac{k(n-p-1)}{k-2}$

求证：每个 5 连通简单可平面图至少有 12 个顶点

证明：$5\le \kappa (G)\le \delta (G)$$5 \le \kappa(G) \le \delta(G)$

根据握手定理得：$2m\ge n\delta (G)\ge 5n$$2m \ge n\delta(G) \ge 5n$

根据简单连通平面图有：$m\le 3n-6$$m \le 3n - 6$

整理得：$5n\le 2m\le 6n-12$$5n \le 2m \le 6n - 12$

化简得：$n\ge 12$$n \ge 12$

所以每个 5 连通简单可平面图至少有 12 个顶点