HW02

Build-Up Error?

• What is wrong with the following “proof”? In addition to finding a counterexample, you should explain what is fundamentally wrong with this approach, and why it demonstrates the danger of build-up error.
• False Claim: If every vertex in an undirected graph has degree at least 1, then the graph is connected.
• 错误声明：如果无向图中每个顶点的度数至少为 1，那么该图是连通的。

---

• Proof
  Base case: There is only one graph with a single vertex and it has degree 0. Therefore, the base case is vacuously true, since the if-part is false.
  Inductive hypothesis: Assume the claim is true for some \(n ≥ 1\).
  Inductive step: We prove the claim is also true for \(n+1\). Consider an undirected graph on \(n\) vertices in which every vertex has degree at least 1. By the inductive hypothesis, this graph is connected. Now add one more vertex x to obtain a graph on \((n + 1)\) vertices.
  All that remains is to check that there is a path from \(x\) to every other vertex \(z\). Since x has degree at least 1, there is an edge from \(x\) to some other vertex; call it \(y\). Thus, we can obtain a path from \(x\) to \(z\) by adjoining the edge \({x, y}\) to the path from \(y\) to \(z\). This proves the claim for \(n + 1\).
  

---

对于顶点数为\(2n\)的图，即可以通过两两配对连接来实现每个顶点的度最少为1而不连通。更一般地说，这是归纳证明中一个积累误差的例子，通常这源于一个错误的假设。
避免意外积累误差的一种方法是在归纳步骤中使用"shrink down,grow back"过程，从\(n+1\)的图开始，删除一个顶点，然后将归纳假设用于较小的图，再加回顶点并证明\(P(n+1)\)成立。
在本例中，删掉一个顶点后可能出现顶点度为0的情况，故归纳假设不成立！

Proofs in Graphs

• Consider a connected graph G with n vertices which has exactly 2m vertices of odd degree, where m > 0. Prove that there are m walks that together cover all the edges of G (i.e., each edge of G occurs in exactly one of the m walks, and each of the walks should not contain any particular edge more than once).
• 考虑一个有 n 个顶点的图 G，它包含 2m 个奇数顶点，证明有 m 条 walk 路径共同覆盖了图 G 的所有边。

---

证明：
我们将\(2m\)个奇数度顶点分为两组，在每一组两两配对的顶点之间添加一条边，则现在所有顶点都是偶数度顶点，根据先前证明的定理，具有Eulerian tour，现在删去添加的边，得到的就是覆盖G所有边的walk的集合

---

• Prove that any graph G is bipartite if and only if it has no tours of odd length.
• 证明当且仅当图 G 没有奇数长度的 tour 时，G 是二分的。

---

证明：
必要性：当图G是二分的，由于只存在两组顶点之间的边，我们将tour中从某个顶点出发的边与回到该顶点的边进行配对，再将从\(R\)中的顶点到\(L\)中顶点的路径与下一条从\(L\)中顶点到\(R\)中顶点的路径两两配对，则所有的tour必然是偶数长度的；
充分性：当G不包含奇数长度的tour，我们可以将G中的所有顶点分成两个不相交的集合

\( R = \{ u \mid \text{the shortest path from } u \text{ to } v \text{ is even} \} \)

\( L = \{ u \mid \text{the shortest path from } u \text{ to } v \text{ is odd} \} \)

我们假设有顶点\(u1, u2 ∈ L\)是相邻的，那么\(tour：从v到u1，u1到u2，u2到v\)均为奇数长度，故tour为奇数长度，与假设矛盾，故\(L\)中没有相邻的顶点；
同样的，我们可以证明\(R\)中没有相邻的顶点；
而G又是连通的，因此G是二分的。