图论作业 3

一、填空题

1. 完全图 $K_{2n}$$K_{2n}$ 共有 $(2n-1)!!$$(2n-1)!!$ 个不同的完美匹配

$K_{2n}$$K_{2n}$ 有 $(2n-1)!!$$(2n-1)!!$ 个不同的完美匹配

$K_{n,n}$$K_{n,n}$ 有 $n!$$n!$ 个不同的完美匹配

2. 超方体 $Q_6$$Q_6$ 的最小覆盖包含的点数为 $32$$32$

考点：定理 62 (König 1931)：在偶图中，最大匹配中的边数等于最小覆盖中的点数

注意 1：如果最小覆盖中的点数不好求，可以求最大匹配中的边数

注意 2：推论：若 $G$$G$ 是 $k$$k$ 正则偶图 $(k>0)$$(k>0)$，则 $G$$G$ 有完美匹配

注意 3：每个 $n$$n$ 方体都有完美匹配 $(n\ge 1)$$(n\ge 1)$

$n$$n$ 方体是正则二部图，有完美匹配，且完美匹配的边数为顶点数的一半

3. 图 $K_{m,n}(m\le n)$$K_{m,n}\ (m \le n)$ 的最小覆盖包含的点数为 $m$$m$

考点：定理 62 (König 1931)：在偶图中，最大匹配中的边数等于最小覆盖中的点数

$m\le n$$m \le n$，最大匹配中的边数正好是 $m$$m$

4. 完全图 $K_{60}$$K_{60}$ 能分解为 $59$$59$ 个边不重的一因子之并

考点：因子分解

注意 1：因子分解是历年来考试的重点

注意 2：总结为 $3$$3$ 个方面「有没有」「能不能」「数一数」

先看选择题 4、5、6 和解答题 5

5. 完全图 $K_{61}$$K_{61}$ 能分解为 $30$$30$ 个边不重的二因子之并

考点：因子分解

6. 假定 $G$$G$ 是具有 $n$$n$ 个点、$m$$m$ 条边、$k$$k$ 个连通分支的无圈图，则 $G$$G$ 的荫度为 $1$$1$

考点：荫度 (只需要掌握概念即可)

定义 82：无环图 $G$$G$ 分解为边不重的生成森林的最少数目，称为图 $G$$G$的荫度，记为 $\sigma (G)$$\sigma(G)$

7. 图 $G$$G$ 是由 $3$$3$ 个连通分支 $K_1,K_2,K_4$$K_1,K_2,K_4$ 组成的平面图，则其共有 $4$$4$ 个面

考点：平面图点数、边数、面数的关系

定理 76 (Euler 公式)：设 $G$$G$ 是具有 $n$$n$ 个点，$m$$m$ 条边，$\phi$$\varphi$ 个面的连通平面图，则有 $n-m+\phi =2$$n-m+\varphi =2$

推论：设 $G$$G$ 是具有 $n$$n$ 个点，$m$$m$ 条边，$\phi$$\varphi$ 个面，$k$$k$ 个连通分支的平面图，则 $n-m+\phi =k+1$$n-m+\varphi = k + 1$

这个题目可以画出来，如果是抽象的，利用公式计算即可

如果利用公式计算：$7-7+\phi =3+1⟹\phi =4$$7-7+\varphi=3+1 \Longrightarrow \varphi=4$

8. 设图 $G$$G$ 与 $K_5$$K_5$ 同胚，则至少从 $G$$G$ 中删掉 $1$$1$ 条边才可能使其成为可平面图

思考：若图 $G$$G$ 与 $K_5$$K_5$ 或 $K_{3,3}$$K_{3,3}$ 同胚，则至少从 $G$$G$ 中删去 1 条边才可能使其成为可平面图

注意：如果考试中具体画出了一个图判断是否可平面

第一步：根据 推论：设 $G$$G$ 是具有 $n$$n$ 个点，$m$$m$ 条边的简单平面图且 $n\ge 3$$n\ge 3$，则 $m\le 3n-6$$m\le 3n-6$ 看是否成立

第二步：如果第一步成立，先尝试去画一下

第三步：如果第二步画不出来，再去思考是否和 $K_5$$K_5$ 或 $K_{3,3}$$K_{3,3}$ 同胚

9. 设连通平面图 $G$$G$ 具有 $5$$5$ 个顶点，$9$$9$ 条边，则其面数为 $6$$6$

考点：平面图点数、边数、面数的关系

图是连通图，直接用欧拉公式：$n-m+\phi =2$$n-m+\varphi=2$

所以 $\phi =6$$\varphi=6$

10. 若图 $G$$G$ 是 $10$$10$ 阶极大平面图，则其面数等于 $16$$16$

考点：极大平面图

先看选择题 10

$\phi =2n-4=16$$\varphi = 2n - 4 = 16$

11. 若图 $G$$G$ 是 $10$$10$ 阶极大外平面图，其内部面共有 $8$$8$ 个

考点：极大非平面图

先看选择题 10

$\phi =n-2=8$$\varphi=n-2=8$

二、不定项选择题

1. 关于非平凡树 $T$$T$，下面说法错误的是（ACE）

• A. $T$$T$ 至少包含一个完美匹配 ❌
• B. $T$$T$ 至多包含一个完美匹配
• C. $T$$T$ 的荫度大于 $1$$1$ ❌
• D. $T$$T$ 是只有一个面的平面图
• E. $T$$T$ 的对偶图是简单图 ❌

考点：非平凡树的总结

A 错误：要想存在完美匹配，必须是偶数阶的图

B 正确

C 错误：$T$$T$ 的荫度等于 $1$$1$

D 正确：只有一个面的平面图一定无圈，即肯定是树

E 错误：对偶图中都是自环

2. 下列说法正确的是（ABE）

• A. 三正则的偶图存在完美匹配
• B. 无割边的三正则图一定存在完美匹配
• C. 有割边的三正则图一定没有完美匹配 ❌
• D. 有完美匹配的三正则图一定没有割边 ❌
• E. 三正则哈密尔顿图存在完美匹配

考点：三正则图的总结

A 正确：推论：若 $G$$G$ 是 $k$$k$ 正则偶图 $(k>0)$$(k>0)$，则 $G$$G$ 有完美匹配

B 正确：

C 错误：有割边的三正则图即可能有完美匹配，也可能没有

D 错误：有完美匹配的三正则图可能有割边

E 正确：见选择题 5 的 E 选项

3. 下列说法正确的是（ABCD）

• A. 在偶图中，最大匹配包含的边数等于最小覆盖包含的点数
• B. 任一非平凡正则偶图包含完美匹配
• C. 任一非平凡正则偶图可以 1-因子分解
• D. 偶度正则偶图可以 2-因子分解
• E. 非平凡偶图的最大匹配是唯一 ❌

考点：二部图的总结

A 正确

B 正确 C 正确：推论：若 $G$$G$ 是 $k$$k$ 正则偶图 $(k>0)$$(k>0)$，则 $G$$G$ 有完美匹配

D 正确：只要是偶数度正则图即可，不一定需要二部图；可见选择题 6 的 B 选项

E 错误：不唯一

4. 下列说法错误的是（AF）

• A. 完全图 $K_{101}$$K_{101}$ 包含 1-因子 ❌
• B. 完全图 $K_{101}$$K_{101}$ 包含 2-因子
• C. 完全图 $K_{102}$$K_{102}$ 包含 1-因子
• D. 完全图 $K_{102}$$K_{102}$ 包含 2-因子
• E. 图 $G$$G$ 的一个完美匹配实际上就是它的一个 $1$$1$ 因子
• F. 图 $G$$G$ 的一个 2-因子实际上就是它的一个哈密尔顿圈 ❌

考点：因子分解 --「有没有」问题

A 错误：定理 64：完全图 $K_{2n}$$K_{2n}$ 是 1-可因子化的；1-因子实际上就是完美匹配；若 $G$$G$ 有一个 1-因子 (其边集称为完美匹配)，则显然 $G$$G$ 的阶数是偶数。所以，奇数阶图不能 1-因子分解

B 正确：定理 68：图 $K_{2n+1}$$K_{2n+1}$ 是 $n$$n$ 个 $H$$H$ 圈的并

C 正确：偶数阶的图不仅有 1-因子，还有 1-因子分解

D 正确：阶数 $\ge 3$$\ge 3$ 的完全图就是哈密尔顿图，哈密尔顿图的哈密尔顿圈一定是 2-因子；定理 69：完全图 $K_{2n}$$K_{2n}$ 是一个 1-因子和 $n-1$$n-1$ 个 $H$$H$ 圈的并

E 正确：1-因子的边集对应一个完美匹配；严格来说是错误的：完美匹配对应一个边集，而 1-因子是一个生成子图，这两个不是同一个概念 (考试中不会出现模凌两可的选项)

F 错误：连通的 2-因子才对应哈密尔顿圈

5. 下列说法正确的是（AD）

• A. 方体 $Q_n$$Q_n$ 可以 1-因子分解
• B. 非平凡树可以 1-因子分解 ❌
• C. 无割边的 $3$$3$ 正则图可以 1-因子分解 ❌
• D. 有割边的 $3$$3$ 正则图一定不可以 1-因子分解
• E. 可 1-因子分解的 $3$$3$ 正则图一定是哈密尔顿图 ❌

考点：因子分解 --「能不能」问题

A 正确：考察 $k$$k$ 正则二部图 (好好总结)；推论：若 $G$$G$ 是 $k$$k$ 正则偶图 $(k>0)$$(k>0)$，则 $G$$G$ 有完美匹配；存在完美匹配的图一定包含 1-因子 (不一定可以 1-因子分解，如彼得森图)，去掉一个 1-因子后，剩下的图是 $k-1$$k-1$ 正则偶图，依然存在完美匹配；所以 $k$$k$ 正则偶图一定可以 1-因子分解；$\to 2k$$\rightarrow 2k$ 正则偶图一定可以 2-因子分解

B 错误：可以 1-因子分解的图一定是偶数阶数的正则图

C 错误：推论 (Peterson)：每个没有割边的 3 正则图都有完美匹配；所以一定有 1-因子，但不一定可以 1-因子分解，如彼得森图

D 正确：有割边的 $3$$3$ 正则图即便有 1-因子，也一定不可以 1-因子分解

E 错误：$3$$3$ 正则图的哈密尔顿图一定可以 1-因子分解；但可以 1-因子分解的 $3$$3$ 正则图不一定是哈密尔顿图

6. 下列说法正确的是（ACDE）

• A. 完全图 $K_{2n}$$K_{2n}$ 是 $2n-1$$2n-1$ 个完美匹配的并
• B. 完全图 $K_{2n}$$K_{2n}$ 是 $n$$n$ 个哈密尔顿圈的并 ❌
• C. 完全图 $K_{2n}$$K_{2n}$ 是 $1$$1$ 个完美匹配与 $n-1$$n-1$ 个哈密尔顿圈的并
• D. 若图 $G$$G$ 是 $2k$$2k$ 正则连通图，则 $G$$G$ 可以分解为 $k$$k$ 个二因子的并
• E. 无割边的 $3$$3$ 正则图可以分解为是一个 1-因子与一个 2-因子的并

考点：因子分解 --「数一数」问题

注意：能分解多少个 $k$$k$ 因子的并 = 顶点在原图中的度数 ➗ 顶点在现在图中的度数

A 正确：原图中每个点的度数为 $2n-1$$2n-1$，现在图中每个点的度数为 $1$$1$，所以可以分解成 $(2n-1)/1$$(2n-1)/1$ 个因子的并

B 错误：完全图 $K_{2n+1}$$K_{2n+1}$ 是 $n$$n$ 个哈密尔顿圈的并；可以 1-因子分解的图一定是偶数阶数的正则图；可以 2-因子分解的图一定是偶数度正则图

C 正确：原图中每个点的度数为 $2n-1=2(n-1)+1$$2n-1 = 2(n-1) + 1$

D 正确：可以 2-因子分解的图一定是偶数度正则图

E 正确：推论 (Peterson)：每个没有割边的 3 正则图都有完美匹配；完美匹配对应的就是 1-因子，去掉一个 1-因子后，就剩一个 2-因子

7. 下列说法正确的是（ABCDE）

• A. 完全图 $K_n$$K_n$ 的荫度为 $[n/2]$$[n/2]$，符号 $[]$$[ ]$ 代表向上取整
• B. 完全二部图 $K_{a,b}$$K_{a,b}$ 的荫度为 $[ab/(a+b-1)]$$[ab/(a+b-1)]$，符号 $[]$$[ ]$ 代表向上取整
• C. 非平凡树的荫度为 $1$$1$
• D. 具有 $m$$m$ 条边的 $n$$n$ 阶无环图可以分解为 $m$$m$ 个生成森林的并
• E. 假设 $H$$H$是图 $G$$G$ 的子图，则 $\sigma (H)\le \sigma (G)$$\sigma(H)\le \sigma(G)$

考点：荫度 (只需要掌握概念即可)

该选择题有兴趣的可以看一下，无兴趣的可忽略

言外之意：最多考填空或者不考 😊

8. 下列说法错误的是（C）

• A. 任何平面图都只有一个外部面
• B. 简单平面图中一定有度数不超过 $5$$5$ 的项点
• C. 平面图的各个面的次数之和可能为奇数 ❌
• D. 只有一个面的连通平面图一定是树
• E. 存在一种方法，总可以把平面图的任意一个内部面转化为外部面

考点：平面图

A 正确

B 正确：定理 77：设 $G$$G$ 是简单平面图，则 $\delta \le 5$$\delta \le 5$

C 错误：定理 75：设 $G$$G$ 是具有 $m$$m$ 条边的平面图，则 $\sum _{f\in \mathrm{\Phi }}deg(f)=2m$$\sum\limits_{f \in \Phi}deg(f) = 2m$

D 正确：只有一个面的连通平面图一定无圈，因为圈有内部和外部

E 正确：

9. 下列说法正确的是（ABCD）

• A. 若无环图 $G$$G$ 是 $2$$2$ 连通的平面图，则其一定不包含割点
• B. 若无环图 $G$$G$ 是 $2$$2$ 连通的平面图，则其一定不包含割边
• C. 若无环图 $G$$G$ 是 $2$$2$ 连通的平面图，则其一定不包含只属于一个面的边
• D. 若无环图 $G$$G$ 是 $2$$2$ 连通的平面图，则其每个面的边界均为圈

A 正确：$2$$2$ 连通，一定没有割点

B 正确：$2$$2$ 连通，一定 $2$$2$ 边连通，一定没有割边；可见作业 2 选择题 6 的 B 选项

C 正确：对于平面图来说，割边就是只属于一个面的边

D 正确：如果不是圈，就有割点

10. 下列说法错误的是（D）

• A. 若 $(n,m)$$(n, m)$ 图 $G$$G$ 是极大平面图且 $n\ge 3$$n \ge 3$，则 $m=3n-6$$m=3n-6$
• B. 若 $(n,m)$$(n, m)$ 图 $G$$G$ 是极大外平面图且 $n\ge 3$$n \ge 3$，则 $m=2n-3$$m=2n-3$
• C. 阶数至少为 $3$$3$ 的极大平面图的每个面均是三角形
• D. 阶数至少为 $3$$3$ 的极大外平面图的每个面均是三角形 ❌
• E. 阶数至少为 $3$$3$ 的极大外平面图一定是哈密尔顿图

考点：极大平面图 + 极大非平面图

「极大平面图的三角形特征」，即每个面 (内部面 + 外部面) 的边界是三角形；定理 81：设 $G$$G$ 是至少有 3 个顶点的平面图，则 $G$$G$ 是极大平面图的充分必要条件为 $G$$G$ 中各面次数均为 3 且为简单图

推论：设 $G$$G$ 是一个有 $n$$n$ 个点，$m$$m$ 条边，$\phi$$\varphi$ 个面的极大平面图，且 $n\ge 3$$n\ge 3$，则 (1) $m=3n-6$$m = 3n - 6$；(2) $\phi =2n-4$$\varphi = 2n - 4$

极大外平面图的外部面的边界是由多边形组成，内部面均由三角形围成

极大外平面图就是在 $N$$N$ 边形的基础上，添加 $n-3$$n-3$ 条不相交的边，把它分成了不相交的 $n-2$$n-2$ 个三角形的并，所以 $m=n+n-3=2n-3$$m=n+n-3=2n-3$；$\phi =n-2+1$$\varphi=n-2+1$，即 $n-2$$n-2$ 个内部面➕ $1$$1$ 个外部面

A 正确 B 正确 C 正确

D 错误：外部面是哈密尔顿圈，不一定是三角形

E 正确

11. 关于平面图 $G$$G$ 和其对偶图 $G^{\ast }$$G^*$ 的关系，下列说法错误的是（DEF）

• A. $G^{\ast }$$G^*$ 是连通平面图
• B. $G^{\ast }$$G^*$的顶点数等于 $G$$G$ 的面数
• C. $G^{\ast }$$G^*$ 的边数等于 $G$$G$ 的边数
• D. $G^{\ast }$$G^*$的面数等于 $G$$G$ 的点数 ❌
• E. $G^{\ast }\cong G$$G^* \cong G$ ❌
• F. 若 $G_1\cong G_2$$G_1 \cong G_2$，则 $G_1^{\ast }\cong G_2^{\ast }$$G_1^* \cong G_2^*$ ❌

考点：「平面图」+「对偶图」知识梳理

A 正确：平面图的对偶图一定是连通的平面图

B 正确 C 正确

D 错误 E 错误：图 $G$$G$ 必须连通才满足

F 错误

三、解答题

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

考点：一个结论的应用

注意： 解答题 1 & 4 的类型最喜欢出

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

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

注意： 下面要证明图 $G$$G$ 是正则二部图，因为「推论：若 $G$$G$ 是 $k$$k$ 正则偶图 $(k>0)$$(k>0)$，则 $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$ 对，使得每队中的男士和女士彼此相识

2. 由于在考试中获得好成绩，$6$$6$ 名学生将获得下列书籍的奖励，分别是:代数学 (a)、微积分 (c)、微分方程 (d)、几何学 (g)、数学史 (h)、规划学 (p)、拓扑学 (t)。每门科目只有 $1$$1$ 本书，而每名学生对书的喜好是：A: d,h,t； B: h,t；C: c,d,g,p；D: d,h；E: d,t；F: a,c,d

   每名学生是否都可以得到他喜欢的书？为什么？（用图论方法求解）

考点：定理 60 (Hall 1935)：设 $G$$G$ 为具有二分类 $(X,Y)$$(X,Y)$ 的偶图，则 $G$$G$ 包含饱和 $X$$X$ 的每个顶点的匹配当且仅当 $|N(S)|\ge |S|$$|N(S)|\ge |S|$ 对所有 $S\subseteq X$$S \subseteq X$ 成立

解：以学生和书籍作为顶点，两个顶点之间连一条边当且仅当该名学生喜欢这本书，得到图记为 $G$$G$，图 $G$$G$ 显然是一个二部图

原问题转换成判断图 $G$$G$ 中是否存在可以饱和学生顶点集的最大匹配

在学生顶点集中可以找到 $4$$4$ 个顶点 $S=\{A,B,D,E\}$$S=\{A,B,D,E\}$，其邻集为 $N(S)=\{d,h,t\}$$N(S)=\{d,h,t\}$，满足 $|N(S)|<|S|$$|N(S)|<|S|$

由 Hall 定理知，图 $G$$G$ 中不存在可以饱和学生集合的最大匹配

因此，每名学生不都可以得到他喜欢的书

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

考点：定理 62 (König 1931)：在偶图中，最大匹配中的边数等于最小覆盖中的点数

证明：因为顶点的最大度为 $\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$ 条边

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

考点：定理 62 (König 1931)：在偶图中，最大匹配中的边数等于最小覆盖中的点数

显然，上图是二部图

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

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

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

所以该覆盖是最小覆盖

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

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

注意 1：关于能不能 k-因子分解，只讲过「1-因子分解」和「2-因子分解」，所以其他因子分解全部需要转化成「1-因子分解」和「2-因子分解」

注意 2：根据阶数分为两类「偶数阶图」「奇数阶图」；「偶数阶图」可以 1-因子分解，「奇数阶图」可以 2-因子分解

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

证明：设 $\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-因子分解

---

扩展：完全图 $K_{4n+1}$$K_{4n+1}$ 的因子分解

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

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

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

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

6. (考过) 设简单图 $G$$G$ 有 $10$$10$ 个 $4$$4$ 度顶点和 $8$$8$ 个 $5$$5$ 度顶点，其余顶点度数均为 $7$$7$。求 $7$$7$ 度顶点的最大数目，使得 $G$$G$ 保持其可平面性

考点：握手定理 + 简单平面图 $m\le 3n-6$$m\le 3n-6$

解：假设 $7$$7$ 度顶点有 $x$$x$ 个，则 $n=10+8+x$$n = 10 + 8 + x$

根据握手定理得：$10\times 4+8\times 5+7x=2m$$10 \times 4 + 8 \times 5 + 7x = 2m$

又因为简单平面图满足 $m\le 3n-6$$m\le 3n-6$

得：$x\le 16$$x \le 16$

所以 $7$$7$ 度顶点的最大数目为 $16$$16$

7. 设 $G^{\ast }$$G^*$ 是具有 $k(k\ge 2)$$k\ (k \ge2)$ 个连通分支的平面图 $G$$G$ 的对偶图，已知 $G$$G$ 的边数为 $10$$10$，面数为 $3$$3$，求 $G^{\ast }$$G^*$ 的面数

解：因为图 $G$$G$ 的边数为 $10$$10$，面数为 $3$$3$，所以对偶图点数为 $3$$3$，边数为 $10$$10$

又因为对偶图一定是连通的，根据欧拉公式：$n-m+\phi =2$$n-m+\varphi=2$

得：$\phi =9$$\varphi = 9$

8. 富勒烯图 (Fullerene graph) 是一种只包含五边形面和六边形面的三正则平面图。试求富勒烯图的五边形面的个数

解：设五边形面和六边形面的个数分别是 $F_5$$F_5$ 和 $F_6$$F_6$

可知，在富勒烯图中，每个顶点被 $3$$3$ 个面共用，每条边被 $2$$2$ 个面共用

$$\begin{array}{c}\{\begin{array}{c}n=|V|=(5F_5+6F_6)/3\\ m=|E|=(5F_5+6F_6)/2\\ \phi =F_5+F_6\end{array}\end{array}$$

根据欧拉公式：$n-m+\phi =2$$n-m+\varphi=2$；得：$F_5=12$$F_5=12$

所以五边形面又 $12$$12$ 个