
%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
问题1. $n$ 为何值时,完全图 $K_n$ 是圈? $n$ 为何值时, $K_n$ 是一条链? 当 $m, n$ 为何值时,完全偶图 $K_{m, n}$ 是圈?
%%<SOLUTION>%%
$n(n \geqslant 2)$ 为奇数时, $K_n$ 是圈; $n=2$ 时, $K_2$ 是链.
当 $m, n$ 均为偶数时, $K_{m, n}$ 是圈.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
问题2. 已知图 $G$ 至少要 $k$ 笔才能画成, 删去一边后得到图 $G^{\prime}$, 问 $G^{\prime}$ 至少需要几笔才能画成?
%%<SOLUTION>%%
设 $G$ 至少有 $2 k$ 个奇顶点, 删去一边得 $G^{\prime}$, 有三种情况: (1) $G^{\prime}$ 的奇顶点数少 2 个, 则 $G^{\prime}$ 至少需 $k-1$ 笔画成; (2) $G^{\prime}$ 的奇顶点数多 2 个, $G^{\prime}$ 至少需 $k+1$ 笔画成; (3) $G^{\prime}$ 的奇顶点数不变, $G^{\prime}$ 至少需 $k$ 笔画成.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
问题3. 判断如图(<FilePath:./figures/fig-c5p3.png>)中的两个图形是否能一笔画.
%%<SOLUTION>%%
这两个图都能一笔画.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
问题4. 在圆上任取 $n(n>2)$ 个点, 把每个点用线段与其余各点相连接, 能否一笔画出所有这些线段,使它们首尾相接,最后回到出发点?
%%<SOLUTION>%%
当 $n$ 是奇数时可以画成; 当 $n$ 是偶数时不能画成.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
问题5. 如果在一次会议上, 每个人都至少与 $\delta \geqslant 2$ 个人交换过意见, 证明一定可以找到 $k$ 个人 $v_1, v_2, \cdots, v_k$, 使得 $v_1$ 与 $v_2$ 交换过意见, $v_2$ 和 $v_3$ 交换过意见, $\cdots, v_{k-1}$ 与 $v_k$ 交换过意见, $v_k$ 与 $v_1$ 交换过意见.
其中 $k$ 为大于 $\delta$ 的某个整数.
%%<SOLUTION>%%
作图 $G$ : 顶点表示人, 两人交换过意见就在相应的顶点之间连一条边.
在 $G$ 中取一条最长的链 $\mu$, 设 $\mu$ 的一个端点为 $v_1$, 则与 $v_1$ 相邻的 $\delta$ 个点 $v_2, \cdots$, $v_{\delta+1}$ 均在链 $\mu$ 上, 否则 $\mu$ 还可延长.
沿着链 $\mu$ 走过 $v_2, v_3, \cdots, v_{\delta+1}$, 然后再回到 $v_1$, 这就是一个长度大于 $\delta$ 的圈.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
问题6. 如图(<FilePath:./figures/fig-c5p6.png>)所示, 图 $G$ 有 4 个顶点, 6 条边, 它们都在同一平面上, 这个平面被 6 条边分成 4 个区域 I, II, III, IV, 称这些区域为面.
设有两个点 $Q_1, Q_2$ 在这些面中, 证明平面上不存在一条连接 $Q_1$ 与 $Q_2$ 的线 $\mu$ 同时满足: (1) $\mu$ 截每条边 $e_i$ 恰好一次 $(i=1,2, \cdots, 6)$; (2) $\mu$ 不过任一顶点 $v_j(j=1,2$, $3,4)$.
%%<SOLUTION>%%
如图(<FilePath:./figures/fig-c5a6.png>), 在每个面中取一点 $v_j^{\prime}(j=1,2,3,4)$, 如果两个面有公共边, 则在所取的两个点之间连一条边, 这样得到的图 $G^*$ 称为 $G$ 的对偶图.
在 $G$ 中, 从一个面穿过某条边 $e_i$ 到另一个面, 就相当于在 $G^*$ 中从一个顶点沿一条边到另一个顶点.
因此, 若 $G$ 中有满足条件 (1)、(2) 的折线 $\mu$ 存在, 那么 $G^*$ 就是一条链 $\left(Q_1, Q_2\right.$ 不在同一面内) 或一个圈 $\left(Q_1, Q_2\right.$ 在同一面内), 即 $G^*$ 可以一笔画成.
但 $G^*$ 的 4 个顶点全是奇顶点, 至少需两笔才能画成.
%%PROBLEM_END%%



%%PROBLEM_BEGIN%%
%%<PROBLEM>%%
问题7. 如图(<FilePath:./figures/fig-c5p7.png>), 在上面由 25 个小正方形组成的图形中,试设计一条从 $A$ 点出发的路径, 走过所有小正方形的边, 最后回到 $A$ 点, 并且使得路径最短.
%%<SOLUTION>%%
如图(<FilePath:./figures/fig-c5a7.png>), 所给的图有 16 个奇顶点 $B_i, C_i(i=1,2, \cdots, 8)$. 如果要使它是一个圈, 至少要加 8 条边.
如图所添加的 8 条边 $B_i C_i(i=1,2, \cdots, 8)$ 后, 能使得该图是一个圈, 图中所示的圈使得路径最短.
%%PROBLEM_END%%


