平面性与图补、超立方体周游、二叉树、边染色、模运算练习、Wilson 定理

(a) 若 \(G\) 有 \(v\) 个顶点，则图中可能存在的边总数为 \(\binom{v}{2} = \frac{v(v-1)}{2}\)。由于其中 \(e\) 条边出现在 \(G\) 中，剩余的 \(\frac{v(v-1)}{2} - e\) 条边必出现在 \(\overline{G}\) 中。

(b) 由于 \(G\) 是平面图，有 \(e \le 3v - 6\)。代入 (a) 的结论，\(\overline{G}\) 至少有 \(\frac{v(v-1)}{2} - (3v - 6)\) 条边。因为 \(v \ge 15\)，所以 \(\frac{v(v-1)}{2} \ge \frac{v \cdot 14}{2} = 7v\)，于是 \(\overline{G}\) 至少有 \(7v - 3v + 6 = 4v + 6\) 条边。由于 \(4v + 6\) 严格大于平面图所允许的 \(3v - 6\) 条边，因此 \(\overline{G}\) 必不是平面图。

(c) 逆命题不一定成立。作为反例，设 \(G\) 恰有 15 个顶点，其中 5 个顶点两两相连，其余 10 个顶点均不与任何顶点相连。这意味着 \(G\) 是非平面图，因为它包含 \(K_5\) 副本。然而 \(\overline{G}\) 也包含一个 \(K_5\) 副本（取自 \(G\) 中孤立的 10 个顶点中的任意 5 个），所以 \(\overline{G}\) 也是非平面图。因此，\(G\) 和 \(\overline{G}\) 可以同时为非平面图。

(a) 在 \(n\) 维超立方体中，每个顶点的度数均为 \(n\)。若 \(n\) 为奇数，则由欧拉定理可知不存在欧拉环游。另一方面，超立方体是连通的：我们可以通过逐位翻转不同的比特，从任意一个二进制串 \(x\) 到达另一个二进制串 \(y\)。因此，当 \(n\) 为偶数时，由于每个顶点的度数均为偶数且图是连通的，故存在欧拉环游。

(b) 对 \(n\) 进行归纳。当 \(n = 1\) 时，两个顶点由一条边相连；我们可以通过从一个顶点走到另一个再走回来形成哈密顿环游。

设 \(n \ge 1\) 且 \(n\) 维超立方体存在哈密顿环游。令 \(H\) 为 \(n+1\) 维超立方体，\(H_b\) 为那些首比特为 \(b\) 的串构成的 \(n\) 维子立方体。

由归纳假设，\(n\) 维超立方体上存在某个哈密顿环游 \(T\)。现在考虑 \(H\) 中的如下环游：从 \(H_0\) 中任意一个顶点 \(x_0\) 出发，沿着环游 \(T\) 前进，但跳过最后一步到达 \(y_0\)（即下一步本应回到 \(x_0\)）。接着沿边从 \(y_0\) 走到 \(y_1\) 进入子立方体 \(H_1\)。然后在 \(H_1\) 中从 \(y_1\) 开始逆着环游 \(T\) 前进，跳过最后一步，到达 \(x_1\)。最后，从 \(x_1\) 走到 \(x_0\) 完成环游。根据假设，环游 \(T\) 在每个子立方体中恰好访问每个顶点一次，因此我们构造出的完整环游在整个立方体中恰好访问每个顶点一次。

为便于理解，以下是前几种情形：

• \(n = 1\)：\(0, 1\)

• \(n = 2\)：\(00, 01, 11, 10\)

[在 0-子立方体（首位为 0 的顶点）中取 \(n=1\) 的环游，移动到 1-子立方体（首位为 1 的顶点），然后倒着走该环游。我们知道 10 与 00 相连以完成环游。]

• \(n = 3\)：\(000, 001, 011, 010, 110, 111, 101, 100\)

[在 0-子立方体中取 \(n=2\) 的环游，移动到 1-子立方体，然后倒着走该环游。我们知道 100 与 000 相连以完成环游。]

用这种方法生成的序列被称为格雷码（Gray code）。

(a) 由于 \(r\) 的度数为 2，移除它会将 \(T\) 分裂为两个连通分量，记为 \(L\) 和 \(R\)。由对称性，只需证明 \(L\) 是二叉树。

不妨设 \(u \in L\)。在移除 \(r\) 之前，\(u\) 的度数必为 1 或 3。若 \(u\) 的度数为 1，则移除 \(r\) 后，\(u\) 成为单独的顶点，是高度为 0 的二叉树，同时也是根。若 \(u\) 的度数为 3，则移除 \(r\) 后，\(u\) 的度数为 2，且 \(L\) 中其余顶点的度数为 1 或 3。因此，\(L\) 是以 \(u\) 为根的二叉树；同理可证 \(R\) 是以 \(v\) 为根的二叉树。

为证明 \(h(T) = \max(h(L), h(R)) + 1\)，我们注意到由于 \(T\) 是树，从 \(r\) 到任意叶节点的路径必经过 \(u\) 或 \(v\) 之一但不会同时经过两者。这意味着从 \(r\) 到任意叶节点的最大距离等于 1 加上从 \(u\) 到 \(L\) 中任意叶节点的最大距离或从 \(v\) 到 \(R\) 中任意叶节点的最大距离（因为路径不能折返经过 \(r\)）。形式化地，若记 \(\mathcal{L}(L)\) 和 \(\mathcal{L}(R)\) 分别为 \(L\) 和 \(R\) 中叶节点的集合，\(d(r, l)\) 为从 \(r\) 到叶节点 \(l\) 的路径长度，则

\[h(T) = 1 + \max\left(\max_{l \in \mathcal{L}(L)} d(u, l), \max_{l \in \mathcal{L}(R)} d(v, l)\right) = 1 + \max(h(L), h(R)).\]

(b) 对二叉树的高度进行归纳。

基础情形：高度为 0 的二叉树是单独一个顶点，有 \(2^1 - 1 = 1\) 个顶点。

归纳假设：设对所有 \(k < h\)，高度为 \(k\) 的二叉树至多有 \(2^{k+1} - 1\) 个顶点。

归纳步骤：由 (a)，从二叉树中移除根可得到两棵二叉树 \(L\) 和 \(R\)，高度分别为 \(k\) 和 \(l\)。由于 \(h(T) = \max(h(L), h(R)) + 1\)，有 \(k, l \le h - 1\)，可对 \(L\) 和 \(R\) 应用归纳假设。因此，\(T\) 的顶点数至多为

\[\underbrace{(2^{k+1} - 1)}_{\text{来自 } L} + \underbrace{(2^{l+1} - 1)}_{\text{来自 } R} + \underbrace{1}_{\text{根}} \le 2^{(h-1)+1} + 2^{(h-1)+1} - 1 = 2^{h+1} - 1.\]

(c) 对二叉树的叶节点数进行归纳。

基础情形：若二叉树只有一个叶节点，则它是单独一个顶点，有 \(1 = 2 \cdot 1 - 1\) 个顶点。

归纳假设：设对所有 \(k < n\)，具有 \(k\) 个叶节点的二叉树有 \(2k - 1\) 个顶点。

归纳步骤：对具有 \(n > 1\) 个叶节点的二叉树 \(T\)，移除根 \(r\) 并将 \(T\) 拆分为二叉树 \(L\) 和 \(R\)。设 \(L\) 有 \(a\) 个叶节点，\(R\) 有 \(b\) 个叶节点。注意到 \(T\) 的所有叶节点都在 \(L\) 或 \(R\) 中，因为 \(n > 1\) 意味着根不是叶节点，所以 \(a + b = n\)。由归纳假设，\(L\) 有 \(2a - 1\) 个顶点，\(R\) 有 \(2b - 1\) 个顶点，因此 \(T\) 的顶点数为

\[\underbrace{(2a - 1)}_{\text{来自 } L} + \underbrace{(2b - 1)}_{\text{来自 } R} + \underbrace{1}_{\text{根}} = 2(a + b) - 1 = 2n - 1.\]

(a) 对三角形 \(u_1, u_2, u_3\) 进行 3-边染色，其中 \((u_1, u_2)\) 染颜色 1，\((u_2, u_3)\) 染颜色 2，\((u_3, u_1)\) 染颜色 3。这是一个合法的 3-染色，因为各边颜色均不同。

现在加入第四个顶点 \(v\)，其关联边必须染不同颜色，且每条关联边 \((v, u_i)\) 的颜色必须与已经和 \(u_i\) 关联的边的颜色不同。具体而言，可以将 \((v, u_1)\) 染成颜色 2（因为它不与染颜色 2 的边关联，且该颜色可用）。类似地，将边 \((v, u_2)\) 染成颜色 3，将 \((v, u_3)\) 染成颜色 1。

另一种证明方式就是直接给出如下染色：三角形 \((u_1, u_2)\) 颜色 1、\((u_2, u_3)\) 颜色 2、\((u_3, u_1)\) 颜色 3；顶点 \(v\) 与 \(u_1, u_2, u_3\) 的连线分别染颜色 2、3、1。

(b) 对图的边数 \(n\) 进行归纳，证明如下命题：若图 \(G\) 有 \(n \ge 0\) 条边且任意顶点的最大度数为 \(d\)，则 \(G\) 可用 \(2d - 1\) 种颜色染色。

基础情形（\(n = 0\)）。若图中没有边，则无需染色，命题显然成立。

归纳假设。设 \(n = k \ge 0\) 时命题成立。

归纳步骤。考虑有 \(n = k + 1\) 条边的图 \(G\)。移除任意一条边 \(e\)。注意到在所得图中，任意顶点的最大度数为 \(d' \le d\)。由归纳假设，可用 \(2d' - 1\) 种颜色染色，因此也可用 \(2d - 1\) 种颜色染色。被移除的边与两个顶点关联，每个顶点至多与另外 \(d - 1\) 条边关联，因此至多有 \(2(d-1) = 2d - 2\) 种颜色对边 \(e\) 不可用。于是，我们可以在无冲突的情况下为边 \(e\) 染色。这证明了 \(n = k + 1\) 时命题成立，由归纳法可知命题对所有 \(n \ge 0\) 成立。

(c) 对树的顶点数 \(n\) 进行归纳，证明如下命题：对于有 \(n \ge 1\) 个顶点的树，若任意顶点的最大度数为 \(d\)，则该树可用 \(d\) 种颜色染色。

基础情形（\(n = 1\)）。若只有一个顶点，则没有边需要染色，因此可用 0 种颜色染色。

归纳假设。设 \(n = k \ge 1\) 时命题成立。

归纳步骤。移除树中任意一个叶节点 \(v\)。由归纳假设，剩余树可用 \(d\) 种颜色染色。对于顶点 \(v\) 的任意邻居 \(u\)，由于移除了边 \(\{u, v\}\) 及顶点 \(v\)，\(u\) 的度数至多为 \(d - 1\)，因此其关联边至多使用了 \(d - 1\) 种颜色，总有一种颜色可用于为边 \(\{u, v\}\) 染色。这完成了归纳步骤，由归纳法可知命题对所有 \(n \ge 1\) 成立。

(a) 两边减去 5 得：

\[9x \equiv 2 \pmod{13}.\]

由于 \(\gcd(9, 13) = 1\)，9 在模 13 下有（唯一）逆元，且因为 \(9 \times 3 = 27 \equiv 1 \pmod{13}\)，所以逆元为 3。两边同乘 \(9^{-1} \equiv 3 \pmod{13}\) 得：

\[x \equiv 6 \pmod{13}.\]

(b) 注意到任意 \(y \equiv 4 \pmod{21}\) 的数可写成 \(y = 4 + 21k\)（\(k\) 为整数）。计算 \(y\) 模 3 的值，得 \(y \equiv 1 \pmod{3}\)。

由于方程右边模 3 余 1，左边也必须模 3 余 1。然而对任意 \(x\)，\(3x + 12\) 都不可能模 3 余 1。因此不存在任何解。

(c) 首先，将第一式从第二式的 4 倍中减去：

\[4(2x + y) - (5x + 4y) \equiv 4(4) - 0 \pmod{7}\] \[8x + 4y - 5x - 4y \equiv 16 \pmod{7}\] \[3x \equiv 2 \pmod{7}\]

两边同乘 \(3^{-1} \equiv 5 \pmod{7}\)，得 \(x \equiv 10 \equiv 3 \pmod{7}\)。

代入第二式，得

\[2(3) + y \equiv 4 \pmod{7},\]

因此方程组的解为 \(x \equiv 3 \pmod{7}\)，\(y \equiv 5 \pmod{7}\)。

(d) 利用 \(13 \equiv 1 \pmod{12}\)，可改写为

\[x \equiv 13^{2023} \equiv 1^{2023} \equiv 1 \pmod{12}.\]

(e) 解指数运算问题的一种方法是逐次测试值直到发现规律。

\[7^1 \equiv 7 \pmod{11}\] \[7^2 \equiv 49 \equiv 5 \pmod{11}\] \[7^3 = 7 \cdot 7^2 \equiv 7 \cdot 5 \equiv 2 \pmod{11}\] \[7^4 = 7 \cdot 7^3 \equiv 7 \cdot 2 \equiv 3 \pmod{11}\] \[7^5 = 7 \cdot 7^4 \equiv 7 \cdot 3 \equiv 10 \equiv -1 \pmod{11}\]

理论上可以继续直到序列开始重复。但注意到若 \(7^5 \equiv -1\)，则 \(7^{10} = (7^5)^2 \equiv (-1)^2 \equiv 1 \pmod{11}\)。

类似地，\(7^{60} = (7^{10})^6 \equiv 1^6 \equiv 1 \pmod{11}\)。最后一步，\(7^{62} = 7^2 \cdot 7^{60} \equiv 7^2 \cdot 1 = 49 \equiv 5 \pmod{11}\)。

(a) 逐一验证，模 7 下的完全立方数只有 0、1 和 6（即 \(-1\)）：

\[0^3 \equiv 0 \pmod{7}, \quad 4^3 \equiv 1 \pmod{7}\] \[1^3 \equiv 1 \pmod{7}, \quad 5^3 \equiv -1 \pmod{7}\] \[2^3 \equiv 1 \pmod{7}, \quad 6^3 \equiv -1 \pmod{7}\] \[3^3 \equiv -1 \pmod{7}\]

(b) 考虑方程 \(x^3 + 2y^3 \equiv 0 \pmod{7}\)，穷举 \(x^3\) 和 \(y^3\) 的所有情况，\(x^3 + 2y^3 \equiv 0 \pmod{7}\) 成立的唯一可能是 \(x^3 \equiv y^3 \equiv 0 \pmod{7}\)。因此 \(x \equiv y \equiv 0 \pmod{7}\)。

(c) 首先证明：若 \((x, y)\) 是 \(x^3 + 2y^3 = 7x^2y\) 的解，则 \(x = 0\) 蕴含 \(y = 0\)。换言之，若 \(x = 0\)，则解必为平凡解。为说明这一点，设 \(x = 0\)，则 \(y^3 = 0\)，从而 \(y = 0\)。因此，任何非平凡解必有 \(x \neq 0\)，即 \(|x| > 0\)。

若 \((x, y)\) 是原方程的解，则它也是

\[x^3 + 2y^3 \equiv 0 \pmod{7}\]

的解。

由 (b) 知 \(x, y\) 都能被 7 整除，从而 \(x^3, y^3\) 都能被 \(7^3\) 整除。因此，可将原方程整体除以 \(7^3\)，得到

\[\left(\frac{x}{7}\right)^3 + 2\left(\frac{y}{7}\right)^3 = 7\left(\frac{x}{7}\right)^2\left(\frac{y}{7}\right).\]

的确，\((x/7, y/7)\) 是另一个所有值均为整数的解，且 \(|x/7| < |x|\)（因为 \(|x| > 0\)）。这与我们最初的假设——\((x, y)\) 是 \(|x|\) 最小的解——产生了矛盾。（这一假设是合理的，因为 \(|x|\) 是正整数，而非空的正整数集必有最小值。）因此，不存在 \(x^3 + 2y^3 = 7x^2y\) 的非平凡解。

方向 1：若 \(p\) 为素数，则该命题成立。

对于整数 \(1, \ldots, p-1\)，每个数都有逆元。然而，当一个数是自身的逆元时，无法将其与另一个不同的数配对。这种情况发生在 \(x^2 \equiv 1 \pmod{p}\)，即 \(p \mid x^2 - 1 = (x-1)(x+1)\) 时。因此，\(p \mid x-1\) 或 \(p \mid x+1\)，即 \(x \equiv 1 \pmod{p}\) 或 \(x \equiv -1 \pmod{p}\)。

因此，在 \(1\) 到 \(p-1\) 中，逆元等于自身的整数只有 1 和 \(p-1\)。

重新考虑乘积 \((p - 1)! = 1 \cdot 2 \cdots (p - 1)\)。该乘积由 1、\(p-1\) 以及若干对互为逆元的数组成，这样的数对共有 \(\frac{p-1-2}{2} = \frac{p-3}{2}\) 对。每对数的乘积为 1（因为一个数与其逆元的乘积为 1），所以 \((p - 1)! \equiv 1 \cdot (p - 1) \cdot 1 \equiv -1 \pmod{p}\)，得证。

方向 2：该式仅在 \(p\) 为素数时成立（逆否命题：若 \(p\) 不是素数，则该式不成立）。

我们用反证法证明：若某个数 \(p\) 是合数，则 \((p - 1)! \not\equiv -1 \pmod{p}\)。

假设 \((p - 1)! \equiv -1 \pmod{p}\)。这意味着可以将 \((p - 1)!\) 写成 \(p \cdot k - 1\)（\(k\) 为整数）。

由于 \(p\) 不是素数，它有一个素因子 \(q\) 满足 \(2 \le q \le p - 2\)，且可写 \(p = q \cdot r\)。将其代入上面 \((p - 1)!\) 的表达式，得 \((p - 1)! = (q \cdot r)k - 1 = q(rk) - 1\)，即 \((p - 1)! \equiv -1 \pmod{q}\)。然而，我们知道 \(q\) 是 \((p - 1)!\) 中的一项，所以 \((p - 1)! \equiv 0 \pmod{q}\)。由于 \(0 \not\equiv -1 \pmod{q}\)，我们得到了矛盾。