DIS2A/2B about note5

1、Eulerian Tour and Eulerian Walk

• What is the condition that there is an Eulerian walk in an undirected graph ?
• 无向图中存在 Eulerian walk 的条件是什么？

---

• An undirected graph has an Eulerian walk if and only if it is connected (except for isolated vertices) and has at most two odd degree vertices.
• 当且仅当无向图是连通的，并且最多有两个奇数顶点时，它具有 Eulerian walk。

---

证明：
首先，根据Handshake lemma，没有只有一个奇数度顶点的图形；另外，Eulerian tour也是Eulerian walk(有0个奇数度顶点的情况)。 因此我们可以一定程度简化证明。

Handshake lemma: in any planar graph, \(\sum_{i=1}^{f} s_i = 2e \), \(s_i\) means the number of sides of face \(i\).

Only if(必要性)：假设存在一个Eulerian walk，例如从\(u\)开始，到\(v\)结束（\(u\)与\(v\)是不同的），那么这个walk上的所有点都是相互连通的，而 不在此walk中的顶点必然是孤立的。因此除去孤立的顶点，图G是连通的。
If(充分性)：根据之前的讨论，这部分我们只需证明当图G是连通的并且恰好有两个奇数度顶点时，它具有从不同起点和终点的Eulerian walk。下面给出两种方法：
\(Solution1:\)取两个奇数度的顶点\(u\)和\(v\)，并添加一个顶点\(w\)，\(w\)具有两条边\((u,w)\)和\((w,v)\)，则新的图\(G'\)变为了偶数度的图，可以 找到Eulerian tour；
\(Solution2:\)我们先从图\(G\)中去除两个奇数度的顶点\(u\)和\(v\)，而我们知道\(u\)和\(v\)间存在通路（路径1）。先考虑删去节点后的图，该图为偶数度 的图，存在Eulerian tour（路径2），然后我们选择存在公共顶点的两条路径进行拼接，可以得到从\(u\)到\(v\)的Eulerian walk。

2、Coloring Trees

• Prove that all trees with at least 2 vertices have at least two leaves. Recall that a leaf is defined as a node in a tree with degree exactly 1.
• 证明：所有至少含两个顶点的树至少有两个 leave 顶点。

---

证明：
对于任意树\(T=(V,E)\)，其中\(|V| \geq 2 \)，假设\(L\)表示leave顶点的集合，为保证树的连通性，其他非leave节点 的度数至少为2。除此之外，我们知道\(|V|\)顶点的树至少需要\(|V|-1\)条边，则有：
\(2|V|-2 = \sum_{v \in V} \deg(v) = \sum_{v \in L} \deg(v) + \sum_{v \in V \setminus L} \deg(v) \geq |L| + 2 (|V|-|L|)\) \(= 2|V|-|L|\)
则需要\(|L| \geq 2 \)，得证。

---

• Prove that all trees with at least 2 vertices are bipartite: the vertices can be partitioned into two groups so that every edge goes between the two groups.
• 证明：所有至少有两个顶点的树都是二分的。

---

证明：
对顶点数\(n\)进行归纳；
基本情况：\(n=2\)，具有两个顶点的树只有一条边，将两个顶点划分为两个单独的部分，是一个二分图；
归纳假设：假设任意具有\(k\)个顶点的树\((k \geq 2)\)都是二分的；
归纳步骤：考虑树\(T=(V,E)\)，它含有\(k+1\)个顶点。树至少有两个leave，我们去掉一个leave顶点\(u\) 和连接到\(u\)的边\(e\)，得到图\(T-u\)，这是具有\(k\)个顶点的树，并且根据归纳假设是二分的，存在\(V = R ∪ L\)。现在 我们将\(u\)再添加回图中，如果边\(e\)将\(u\)与\(L\)中的顶点连接起来，则有\(L' = L\)且\(R' = R \cup \{u\}\)， 与\(R\)也是同理。这样表明\(T\)也是二分的。

3、Graph Coloring

• Prove that a graph with maximum degree at most k is (k + 1)-colorable.
• 证明：最大度数为 k 的图可以用 k+1 个颜色进行着色。

---

证明：
证明这个定理(命名为\(P(n)\))最自热的方法是对k进行归纳，但最大度数变化时，包含的图形类型很多，难以覆盖。因此在涉及图的证明中，更好的归纳参数选择是\(n\)(节点)或\(e\)(边数)。
基本情况：\(n=1\)，一个顶点的图显然成立，\(P(1)\)为真；
归纳假设：\(P(n)\)为真；
归纳步骤：设\(G\)为最大度为\(k\)的\((n+1)\)顶点图。删除顶点\(v\)及其边，留下\(n\)顶点子图 \(H\)，根据假设\(H\)是\((k+1)\)可着色的；重新加入顶点\(v\)，我们可以为\(v\)分配一个不同于其所有相邻顶点的颜色，即证毕。