树与连通分量、平面性、超立方体

(a) 3。

设原图为 \(G = (V, E)\)，Bob 移除节点后的结果图为 \(G' = (V', E')\)。设 \(|V| = n\)，由树的定义知 \(|E| = n - 1\)。同时，\(|V'| = n - 1\)，\(|E'| = n - 4\)。设 \(k\) 为 \(G'\) 中的连通分量数。由于移除顶点和边不会产生环，因此 \(G'\) 是无环的。从而每个连通分量都是一棵树。设 \(n_1, n_2, \ldots, n_k\) 分别为 \(k\) 个连通分量中的节点数。由树的定义，每个分量分别有 \(n_1 - 1, n_2 - 1, \ldots, n_k - 1\) 条边。因此 \(G'\) 中的总边数为 \[n - 4 = |E'| = \sum_{i=1}^{k} (n_i - 1) = \left(\sum_{i=1}^{k} n_i\right) - k = (n - 1) - k.\] 因此 \(k = 3\)。

另一种解法：这里我们使用这样一个事实：从森林（即无环图）中移除一条边会使连通分量数恰好增加 1。如果我们移除与被移除顶点关联的三条边，会得到 4 个分量。但是 Bob 还移除了度为 3 的顶点本身，而它自身就是四个连通分量之一。因此剩下 3 个连通分量。

(b) 7。

我们首先注意到，在任意连通图中，如果移除一条属于环的边，结果图仍然连通。因此对于任意连通图，我们可以反复移除属于环的边，直到没有环为止。这个过程会产生一个连通无环图，即一棵树。

由于我们希望得到的最终图是无环的，它的每个连通分量必须是一棵树。因此这些分量应分别有 \(n_1 - 1\)、\(n_2 - 1\) 和 \(n_3 - 1\) 条边，其中 \(n_1, n_2, n_3\) 是各分量中的顶点数。设 \(n\) 为顶点总数，则 \(n = n_1 + n_2 + n_3\)。因此最终图中的总边数为 \(n - 3\)。

Bob 和 Alice 操作后的总边数为 \(n - 1 + 10 - 5 = n + 4\)。因此需要移除 7 条边。

(a) 可平面或不可平面。 由四色定理（4-color theorem），任何可平面图都可以作为可平面的例子。最简单的不可平面例子是 \(K_{3,3}\)，它是二分图（bipartite），可以 2-着色。（当然，任何只需 2 种颜色着色的图也可以用 4 种颜色着色。）

(b) 总是不可平面。 四色定理告诉我们，如果一个图是可平面的，它只需 4 种颜色即可着色。其逆否命题是：如果一个图需要超过 4 种颜色进行顶点着色，它一定是不可平面的。（使用五色定理或六色定理也可以。）

(c) 可平面或不可平面。 从笔记中我们知道，每个可平面图都满足这个公式，因此任何可平面图都是有效的可平面例子。最简单的不可平面例子仍是 \(K_{3,3}\)，它有 \(e = 9\) 条边和 \(v = 6\) 个顶点，代入公式得 \(9 \le 3(6) - 6 = 12\)，显然成立。

(d) 总是可平面。 这里有两种情况需要处理：要么 \(G\) 是一棵树，要么 \(G\) 不是树且因此至少包含一个环。在前一种情况下，我们立即得证，因为所有树都是可平面的。在后一种情况下，考虑 \(G\) 中的任意一个环。我们知道该环中每个顶点都与其在环中的左邻和右邻顶点相邻。但我们也知道没有顶点可以连接到超过两个其他顶点，因此该环不与其他任何部分相连。但 \(G\) 是连通图，因此 \(G\) 必须只是一个大环。我们显然可以在平面上画出简单环而不交叉任何边，因此在这种情况下 \(G\) 仍然是可平面的。

或者，我们可以使用库拉托夫斯基定理（Kuratowski's theorem）；由于每个顶点的度至多为 2，\(G\) 不可能包含 \(K_5\) 或 \(K_{3,3}\)。这意味着 \(G\) 必须是可平面的。

(e) 总是可平面。 \(G\) 的每个连通分量都是连通的且没有度超过 2 的顶点，因此由前一部分可知，每个分量都必须是可平面的。因此 \(G\) 的每个连通分量都是可平面的，所以 \(G\) 本身必须是可平面的。

或者，我们可以沿用前述另一种解法的步骤；每个顶点的度仍然至多为 2，因此 \(G\) 不可能包含 \(K_5\) 或 \(K_{3,3}\)。这意味着 \(G\) 必须是可平面的。

(a) 1 维、2 维、3 维超立方体分别是一条线段、一个正方形和一个立方体。具体图示参见注意 5。

(b) 证法一（按比特位着色）： 考虑每条边翻转的是第 \(i\) 个比特位（\(i \leq n\)）。对于任意顶点，恰好只有一条关联边会翻转第 \(i\) 个比特位（因为翻转第 \(i\) 位只有一种方式）。将这类边都着以颜色 \(i\)，则每个顶点所关联的 \(n\) 条边颜色各不相同（分别对应 \(n\) 个不同的比特位），满足要求。

三维情形的示意图如下（红色代表第 1 位，蓝色代表第 2 位，绿色代表第 3 位）：

证法二（归纳法）： 基础情形 \(n=1\) 时，仅含一条线段的超立方体可用 1 种颜色边着色。假设 \(n\) 维超立方体可用 \(n\) 种颜色边着色。回顾 \(n+1\) 维超立方体由两个 \(n\) 维超立方体组成，由归纳假设它们各自可用 \(n\) 种颜色着色。连接两个子超立方体的边着以第 \(n+1\) 种颜色；这些新边连接的是来自不同子立方体的不同顶点对，彼此不共顶点，从而得到 \(n+1\) 维超立方体用 \(n+1\) 种颜色的合法边着色。

(c) 证法一（按 0 的个数奇偶性划分）： 考虑含偶数个 \(0\) 比特的顶点集与含奇数个 \(0\) 比特的顶点集。每条边翻转恰好一个比特，因此要么增加一个 \(0\)（将 \(1\) 翻为 \(0\)），要么减少一个 \(0\)（将 \(0\) 翻为 \(1\)），都会改变 \(0\) 的个数的奇偶性。因此，含偶数个 \(0\) 的顶点只与含奇数个 \(0\) 的顶点相邻。令 \(L\) 为含偶数个 \(0\) 的顶点集，\(R\) 为含奇数个 \(0\) 的顶点集，则任意相邻顶点不属于同一集合，\(G\) 是二分图。

三维情形示意图如下（\(L\) 为蓝色顶点，\(R\) 为红色顶点）：

证法二（归纳法 + 着色）： 一个图是 2-可着色的当且仅当它是二分图。基础情形 \(n=1\) 时，超立方体只有两个顶点，显然 2-可着色。对 \(n+1\) 维超立方体，由归纳假设两个子超立方体各自 2-可着色。将其中一个子立方体的颜色翻转（交换两种颜色），则子立方体内部的边仍连接不同颜色（由归纳假设），而跨子立方体的边连接的是翻转后颜色不同的对应顶点，因此所有边都跨越两种颜色，\(G\) 是二分图。