图论作业 2

一、填空题

1. 图 $G$$G$ 的顶点数为 $n$$n$ 且 $7$$7$ 连通，则其边数至少为 $\lceil \frac{7n}{2}\rceil$$\left \lceil \frac{7n}{2} \right \rceil$

考点：握手定理 + 点连通度 + $k$$k$ 连通

「一个图是 $k$$k$ 连通的，说明点连通度 $\ge k$$\ge k$」「 $\kappa (G)\le \lambda (G)\le \delta (G)$$\kappa (G) \le \lambda (G) \le \delta(G)$」

故有 $\delta (G)\ge \kappa (G)\ge 7$$\delta(G) \ge \kappa(G) \ge 7$

所以：$d(G)\ge 7n$$d(G) \ge 7n$

所以 $m\ge \lceil \frac{7n}{2}\rceil$$m \ge \left \lceil \frac{7n}{2} \right \rceil$

2. 彼得森图的点连通度和边连通度分别为 $3$$3$ 和 $3$$3$

考点：特殊图的点连通度和边连通度

注意：特殊图有：「彼得森图」「$n$$n$ 方图」「二部图」「完全图」

注意：总结特殊图的「点连通度」「边连通度」「点色数」「边色数」

彼得森图是 $3$$3$ 正则图，故有 $\kappa (G)\le \lambda (G)\le \delta (G)=3$$\kappa(G) \le \lambda(G) \le \delta(G) = 3$

彼得森图不是哈密尔顿图，但在彼得森图的基础上删去任意一个顶点后，会变成哈密尔顿图 (经过每个点的圈)；如果再删去一个点，必不会改变图的点连通性，因为已经是圈了，删去一个点顶多把圈变成路。所以必有 $\kappa (G)\ge 3$$\kappa(G) \ge 3$

综上：$\kappa (G)=\lambda (G)=3$$\kappa(G) = \lambda(G) = 3$

3. 非平凡树的点连通度和边连通度分别为 $1$$1$ 和 $1$$1$

对树来说，每条边都是割边，每个分支点 (度数大于 1 的顶点称为分支点) 都是割点

非平凡树首先想到完全 $2$$2$ 阶图，即 $K_2$$K_2$

$K_2$$K_2$ 没有割点，但点连通度为 $1$$1$ (完全图的点连通度是顶点数 $-1$$- 1$)

对于 $n\ge 3$$n \ge 3$ 的非平凡树，肯定有分支点，所以点连通度为 $1$$1$

---

从另一个角度理解，非平凡树每条边都是割边，故 $\lambda (G)=1$$\lambda(G) = 1$

又因为有 $\kappa (G)\le \lambda (G)\le \delta (G)$$\kappa(G) \le \lambda(G) \le \delta(G)$

所以有 $\kappa (G)\le \lambda (G)=1$$\kappa(G) \le \lambda(G) = 1$

故 $\kappa (G)=1$$\kappa(G) = 1$

4. 长度为 $n(n\ge 3)$$n(n\ge3)$ 的圈的 $2$$2$ 宽直径为 $n-1$$n-1$

考点：宽距离 & 宽直径

两个顶点 $x,y$$x,y$ 的 $w$$w$ 宽距离，$x,y$$x,y$ 间找 $w$$w$ 条独立的路，且每条路尽可能的短，$w$$w$ 条路中最长的路就是宽距离

所有点对的 $w$$w$ 宽距离的最大值就是 $w$$w$ 宽直径

对于本题，两个点邻接时，宽距离最大，为 $n-1$$n - 1$，故 $2$$2$ 宽直径为 $n-1$$n -1$

5. 完全图 $K_n(n\ge 5)$$K_n(n\ge5)$ 的 $3$$3$ 宽直径为 $2$$2$

考点：宽距离 & 宽直径

任意两个点 $u,v$$u,v$ 的第一条路直接为相连，即 $uv$$uv$，长度为 $1$$1$

第二条路：任意找一个其他点 $x$$x$，即 $uxv$$uxv$，长度为 $2$$2$

第三条路同理。所以 $3$$3$ 宽直径为 $2$$2$

6. 设图 $G$$G$ 是具有 $k$$k$ 个奇度顶点，则在 $G$$G$ 中最少添加 $\frac{k}{2}$$\frac{k}{2}$ 条边才能使 $G$$G$ 具有欧拉回路

奇度顶点的个数一定是偶数，不然无法满足握手定理

欧拉图的每个顶点的度数一定是偶数

7. 完全偶图 $K_{m,n}(m,n\ge 2$$K_{m,n} (m,n\ge 2$ 且均为偶数 $)$$)$，则在其最优欧拉环游中共含 $mn$$mn$ 条边

最优欧拉环游：包含该图的每条边至少一次，且边权之和最小的闭途径

特别地，对于欧拉图来说，最优欧拉环游就是欧拉回路

完全偶图 $K_{m,n}$$K_{m,n}$ 一定是欧拉图，所以 $K_{m,n}$$K_{m,n}$ 包含的边数为 $mn$$mn$

8. 下图的最优欧拉环游的权值为 $38$$38$

这样的图一定是特殊的图，恰好有一对奇度顶点

我们只需要把这对奇度顶点最短路上的边复制一次即可

9. 具有 $5$$5$ 个点的度极大非哈密尔顿图族为 $C_{1,5}$$C_{1,5}$ 和 $C_{2,5}$$C_{2,5}$

考点：$C_{m,n}$$C_{m,n}$ 图

注意：$C_{m,n}$$C_{m,n}$ 图的结构和性质需要掌握

包含边数最多的非哈密尔顿图只有两类：$C_{1,n}$$C_{1,n}$ 和 $C_{2,n}$$C_{2,n}$

二、不定项选择题

1. 下列说法正确的是（CD）

• A. 有割边的图一定有割点 ❌
• B. 有割点的图一定有割边 ❌
• C. 割点至少属于图的两个块
• D. 割边不在图的任一圈中
• E. 图的割点也是子图的割点 ❌

考点：割边 + 割点

注意 1：提到割边一定要想到「$K_2$$K_2$」；提到割点一定要想到「自环」「八字形的图」「$K_2$$K_2$」；提到块一定要想到「阶数至少为 3」

注意 2：两个不同块的公共顶点只能是割点，即块与块只能由割点相联结，因此可以通过割点搜寻块

A 错误：提到割边想到「$K_2$$K_2$」，有割边无割点

B 错误：提到割点想到「八字形的图」，有割点没有割边

C 正确：定理 33：点 $v$$v$ 是图 $G$$G$ 的割点当且仅当 $v$$v$ 至少属于 $G$$G$ 的两个不同的块

D 正确

E 错误：八字形的图去掉一个块就没有割点

2. 设 $\kappa (G),\lambda (G),\delta (G)$$\kappa(G), \lambda(G), \delta(G)$ 分别表示图 $G$$G$ 的点连通度、边连通度和最小度。下面说法错误的是（D）

• A. 存在图 $G$$G$，使得 $\kappa (G)=\lambda (G)=\delta (G)$$\kappa(G)=\lambda(G)=\delta(G)$
• B. 存在图 $G$$G$，使得 $\kappa (G)<\lambda (G)<\delta (G)$$\kappa(G)<\lambda(G)<\delta(G)$
• C. 设图 $G$$G$ 是 $n$$n$ 阶简单图，若 $\delta (G)\ge n/2$$\delta(G)\ge n/2$，则 $G$$G$ 连通且 $\lambda (G)=\delta (G)$$\lambda(G)=\delta(G)$
• D. 图 $G$$G$ 是 $k$$k$ 连通的，则 $\kappa (G)=k$$\kappa(G)= k$ ❌
• E. 若图 $G$$G$ 是 $k$$k$ 连通的，则 $\lambda (G)\ge k$$\lambda(G) \ge k$

考点：点连通度 + 边连通度 + 最小度「$\kappa (G)\le \lambda (G)\le \delta (G)$$\kappa(G) \le \lambda(G) \le \delta(G)$」

A B 显然正确

C 正确：引理：设 $G$$G$ 是 $n$$n$ 阶简单图，若 $\delta (G)\ge \lfloor n/2\rfloor$$\delta(G) \ge \left\lfloor n/2 \right\rfloor$，则 $G$$G$ 必连通 定理 37：设 $G$$G$ 是 $n$$n$ 阶简单图，若 $\delta (G)\ge \lfloor n/2\rfloor$$\delta(G) \ge \left\lfloor n/2 \right\rfloor$，则 $\lambda (G)=\delta (G)$$\lambda(G)=\delta(G)$

D 错误：$\kappa (G)\ge k$$\kappa(G)\ge k$

E 正确

3. 下面说法正确的是（BDE）

• A. 没有割点的非平凡连通图一定是 $2$$2$ 连通图 ❌
• B. $2$$2$ 连通图一定没有割边
• C. 完全图一定没有割边 ❌
• D. 完全图一定没有割点
• E. 非平凡树一定有割边
• F. 非平凡树一定有割点 ❌

考点：割边 + 割点

A 错误：提到割点想到「$K_2$$K_2$」，是 1 连通图；如果加上限定条件「阶数 $\ge 3$$\ge 3$」就是正确的

B 正确：$2$$2$ 连通图一定是 $2$$2$ 边连通的，一定没有割边；$2$$2$ 连通图阶数一定 $\ge 3$$\ge 3$，有割边一定有割点，故矛盾！

C 错误：提到割边想到「$K_2$$K_2$」；如果加上限定条件「阶数 $\ge 3$$\ge 3$」就是正确的

D 正确

E 正确：非平凡树一定有边，每条边一定是割边

F 错误：提到割点想到「$K_2$$K_2$」

4. 下面说法正确的是（B）

• A. 若图 $G$$G$ 是 $k$$k$ 连通的，则 $G$$G$ 中必存在 $k$$k$ 点割 ❌
• B. 若图 $G$$G$ 是 $k$$k$ 连通的，则 $G$$G$ 也是 $k$$k$ 边连通的
• C. 若图 $G$$G$ 是 $k$$k$ 边连通的，则 $G$$G$ 也是 $k$$k$ 连通的 ❌
• D. 存在最小度为 $3$$3$ 的 $4$$4$ 连通图 ❌
• E. 存在具有 $n$$n$ 个点，$m$$m$ 条边的 $[2m/n+1]$$[2m/n+1]$ 连通图 ❌

考点：点连通度 + 边连通度 + 点割 + 边割

注意：有些图没有点割，但其连通度为 $n-1$$n - 1$

A 错误：完全图 $K_n$$K_n$ 没有点割，但连通度为 $n-1$$n - 1$；换成边割就成立

B 正确 C 错误：$k\le \kappa (G)\le \lambda (G)$$k \le \kappa(G) \le \lambda(G)$

D 错误：最小度为 $3$$3$，其点连通度最多为 $3$$3$

E 错误：$[2m/n+1]$$[2m/n+1]$ 表示「平均度 + 1」，肯定大于最小度

5. 设图 $G$$G$ 是一个块，下列说法错误的是（ABC）

• A. 图中一定有圈 ❌
• B. 图中一定无环 ❌
• C. 图中一定无割边 ❌
• D. 图中一定无割点
• E. 若 $G$$G$ 的阶数大于等于 $3$$3$，则 $G$$G$ 中任意两点必位于某一圈上
• F. 若 $G$$G$ 的阶数大于等于 $3$$3$，则 $G$$G$ 中任意两条边必位于某一圈上
• G. 若 $G$$G$ 的阶数大于等于 $3$$3$，则 $G$$G$ 中没有割边

考点：块

注意：提到块，一定要想到阶数至少为 $3$$3$

• 阶数为 $1$$1$ 的块，要么是孤立点，要么是自环
• 只有一条边的块，要么是自环，要么是 $K_2$$K_2$

A 错误：「$K_2$$K_2$」；B 错误：「自环」；C 错误：「$K_2$$K_2$」

D 正确：块就是没有割点的连通图

E 正确：定理 32：设图 $G$$G$ 的阶至少为 $3$$3$，则 $G$$G$ 是块当且仅当 $G$$G$ 无自环并且任意两点都位于同一个圈上

F 正确：推论：设 $G$$G$ 的阶至少为 $3$$3$，则 $G$$G$ 是块当且仅当 $G$$G$ 无孤立点且任意两条边都在同一个圈上

G 正确：至少有三个点的块无环、无割边

6. 下面说法错误的是（AB）

• A. 顶点度数为偶数的图一定是欧拉图 ❌
• B. 欧拉图一定没有割点 ❌
• C. 欧拉图一定没有割边
• D. 非平凡欧拉图中一定有圈
• E. 至少具有 $2$$2$ 个点的无环欧拉图一定是 $2$$2$ 边连通的

考点：欧拉图

注意：欧拉图和哈密尔顿图都有一个大前提：均为连通图

A 错误：没有说明是否连通，只能确定每个连通分支均为欧拉图

B 错误：八字形的图

C 正确：欧拉图的边集能划分为边不重的圈的并，每条边均在圈上

D 正确：只要有边，就有圈

E 正确：根据 C 选项知欧拉图一定没有割边，所以边连通一定是 $2$$2$

思考 1：两个欧拉图的积图是否还是欧拉图？(是)

思考 2：两个哈密尔顿图的积图是否还是哈密尔顿图？(是)

7. 关于哈密尔顿图，下列命题错误的是（E）

• A. 若 $G$$G$ 是哈密尔顿图，则对于 $V$$V$ 的每个非空顶点真子集 $S$$S$，均有 $\omega (G-S)\le |S|$$\omega(G-S)\le |S|$
• B. 设 $G$$G$ 是阶数为 $n(n\ge 3)$$n(n\ge3)$ 的简单图，若其最小度 $\delta \ge n/2$$\delta \ge n/2$，则 $G$$G$ 是哈密尔顿图
• C. 设 $G$$G$ 是 $n(n\ge 3)$$n(n\ge3)$ 阶的简单图，若 $G$$G$ 中任意两个不邻接点 $u$$u$ 与 $v$$v$，满足 $d(u)+d(v)\ge n$$d(u)+d(v)\ge n$，则 $G$$G$ 是哈密尔顿图
• D. 哈密尔顿图一定没有割边
• E. 哈密尔顿图一定没有割点 ❌

考点：哈密尔顿图

A 正确：定理 44：若 $G$$G$ 是 $H$$H$ 图，则对于 $V$$V$ 的每个非空真子集 $S$$S$，均有 $\omega (G-S)\le |S|$$\omega(G-S)\le|S|$

B 正确：定理 45 (Dirac 1952)：对于 $n\ge 3$$n \ge 3$ 的简单图 $G$$G$，如果 $G$$G$ 中有：$\delta (G)\ge \frac{n}{2}$$\delta(G)\ge \frac{n}{2}$，那么 $G$$G$ 是 $H$$H$ 图

C 正确：定理 46 (Ore 1962)：对于 $n\ge 3$$n \ge 3$ 的简单图 $G$$G$，如果 $G$$G$ 中的任意两个不相邻顶点 $u$$u$ 与 $v$$v$，有：$d(u)+d(v)\ge n$$d(u)+d(v) \ge n$，那么 $G$$G$ 是 $H$$H$ 图

D 显然正确

E 错误：存在自环的哈密尔顿图有割点；哈密尔顿简单图中一定不存在割点

8. 关于哈密尔顿图，下列命题正确的是（ABCE）

• A. 设 $n(n\ge 3)$$n(n\ge3)$ 阶简单图的最小度满足 $\delta \ge n/2$$\delta \ge n/2$，则其闭包一定为完全图
• B. 设 $n(n\ge 3)$$n(n\ge3)$ 阶简单图的任意两个不邻接顶点 $u$$u$ 与 $v$$v$ 满足 $d(u)+d(v)\ge n$$d(u)+d(v)\ge n$，则其闭包一定为完全图
• C. 设 $n(n\ge 3)$$n(n\ge3)$ 阶简单图 $G$$G$ 满足度序列判定定理的条件，则其闭包一定为完全图
• D. 设 $n(n\ge 3)$$n(n\ge3)$ 阶简单图 $G$$G$ 的闭包不是完全图，则它一定是非哈密尔顿图 ❌
• E. 设 $n(n\ge 3)$$n(n\ge3)$ 阶简单图 $G$$G$ 的闭包是完全图，则图 $G$$G$ 是哈密尔顿图

考点：闭包

注意 1：满足 Dirac 定理、Ore 定理、度序列判定定理的图的闭包一定是完全图

注意 2：定理 49 (Bondy)：一个简单图 $G$$G$ 是 $H$$H$ 图当且仅当它的闭包是 $H$$H$ 图

A B C 正确

D 错误：否命题不成立

E 正确： 推论：设 $G$$G$ 是 $n\ge 3$$n\ge 3$ 的简单图，若 $G$$G$ 的闭包是完全图，则 $G$$G$ 是 $H$$H$ 图

9. 关于哈密尔顿图，下列命题错误的是（BD）

• A. 设 $G$$G$ 是阶数为 $n(n\ge 3)$$n(n\ge3)$ 的非哈密尔顿简单图，则 $G$$G$ 度弱于某个 $C_{m,n}$$C_{m,n}$ 图
• B. 图 $G$$G$ 是哈密尔顿图当且仅当其闭包是完全图 ❌
• C. 若 $(m,n)$$(m,n)$ 简单图 $G$$G$ 的边数 $m>(\genfrac{}{}{0ex}{}{n-1}{2})+1$$m > \binom{n-1}{2} + 1$，且 $n>3$$n>3$，则 $G$$G$ 是哈密尔顿图
• D. 若图 $G$$G$ 的闭包是哈密尔顿图，则其闭包一定是完全图 ❌
• E. 设 $G$$G$ 是阶数为 $n(n\ge 3)$$n(n\ge3)$ 的哈密尔顿简单图，若 $n$$n$ 为奇数，则 $G$$G$ 一定不是偶图

考点：哈密尔顿图 + 闭包

A 正确：定理 51 (Chvátal 1972)：若 $G$$G$ 是 $n\ge 3$$n\ge 3$ 的非 $H$$H$ 简单图，则 $G$$G$ 度弱于某个 $C_{m,n}$$C_{m,n}$ 图

B 错误：定理 49 (Bondy)：一个简单图 $G$$G$ 是 $H$$H$ 图当且仅当它的闭包是 $H$$H$ 图

C 正确：推论：设 $G$$G$ 是 $n$$n$ 阶简单图。若 $n\ge 3$$n\ge 3$ 且 $\begin{array}{c}|E(G)|>\left(\begin{array}{c}n-1\\ 2\end{array}\right)+1\end{array}$$|E(G)| >\begin{pmatrix}n-1 \\2\end{pmatrix} + 1$，则 $G$$G$ 是 $H$$H$ 图

D 错误：一个图的闭包不一定是完全图

E 正确：阶数为奇数，则哈密尔顿圈是奇圈；定理 9：一个图是偶图当且仅当它不包含奇圈

三、解答题

1. (去年考过) 证明：设简单图 $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$

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$

3. 在 $8\times 8$$8 \times 8$ 黑白方格相间的棋盘上跳动一只马，这只马能否连续地完成每一种可能的跳动恰好一次？（一只马跳动一次是指从一个长为 $3$$3$，宽为 $2$$2$ 的黑白方格组成的长方形的一个角跳到对角上；在同一个长方形的两个对角之间的相互跳动认为是同一跳动）

关键：建立正确的图论模型

解：以每个方格为顶点，如果两个方格恰好是某个长 $3$$3$ 宽 $2$$2$ 矩形的对角，则这两个方格之间连一条边，我们可以得到一个图，那么该图中的边与马的每一次跳动相对应

现在问题转换为了：能否连续的经过图的每条边恰好一次，即求该图是否存在欧拉迹

图中度数为 $3$$3$ 的顶点有 $8$$8$ 个，根据 推论：连通图 $G$$G$ 有 $Euler$$Euler$ 迹当且仅当 $G$$G$ 最多有两个奇点，显然不存在欧拉迹

---

扩展：能否通过马的跳动遍历完所有的方格？

现在问题转换为了：上述建立模型中的图是否为哈密尔顿图

4. 证明：若 $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$

根据 定理 45 (Dirac 1952)：对于 $n\ge 3$$n \ge 3$ 的简单图 $G$$G$，如果 $G$$G$ 中有：$\delta (G)\ge \frac{n}{2}$$\delta(G)\ge \frac{n}{2}$，那么 $G$$G$ 是 $H$$H$ 图，图 $K$$K$ 一定是哈密尔顿图

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

5. (前年考过) 亚瑟王在王宫中召见他的 $2n$$2n$ 位骑士，其中某些骑士之间互有怨仇。已知每个骑士的仇人不超过 $n-1$$n-1$ 个，证明亚瑟王的谋士摩林能够让这些骑士围着圆桌坐下，使得每一个骑士不与他的仇人相邻

解：以骑士为顶点，如果两个骑士是友好的，那么两个骑士之间连一条边，得到的图记为 $G$$G$

原问题转换为：判断图 $G$$G$ 是否为哈密尔顿图

由题知：$\delta (G)\ge 2n-1-(n-1)=n$$\delta(G) \ge 2n - 1 - (n - 1) = n$

根据 定理 45 (Dirac 1952)：对于 $n\ge 3$$n \ge 3$ 的简单图 $G$$G$，如果 $G$$G$ 中有：$\delta (G)\ge \frac{n}{2}$$\delta(G)\ge \frac{n}{2}$，那么 $G$$G$ 是 $H$$H$ 图，图 $G$$G$ 一定是哈密尔顿图

所以亚瑟王的谋士摩林能够让这些骑士围着圆桌坐下，使得每一个骑士不与他的仇人相邻