3. (pa, i A pb. i), i= l,..., k for all aEb. It means no neighbors have the same color Then we get a set S with infinite propositions. For any finite subset So C X, we can extract vertices Vo from it and construct a set Si which describe the graph Go generated by Vo. For every finite ubgraph is k-colorable, S1 is satisfiable. So must be satisfiable According to compactness theorem, S is satisfiable which means the graph is k-colorable Remark: Generally, this theorem is not easy to prove via graph approach. Because there is no effective way to find it possible that a big graph is still k-colorable merged by two k-colorable graph However, Compactness Theorem does not need this requirement. Here, we should be aware that a set of propositions is constructed and we try to prove that every finite subset of it is satisfiable, which is the essence of Compactness Theorem. Example 6. Every set S can be(totally) ordered nilarly, it can be proved like k-colorable infinite graph. The point is to represent our problem a set of propositions. This is left as an exercise Hints: A set is partial order at least. If you can change a partially ordered set into a linear order 9 Konig Lemma and compactness theorem In our textbook, Compactness Theorem is proved by Konig lemma. Now we will show you that it can be proved by Compactness Theorem Lemma 11(Konig). A infinite tree with finite branch has a infinite path Actually, the problem can be represented as following. If every a E T has only finitely many immediate successor and T contains arbitrarily long finite paths, then there is a infinite path in T starts at root Proof. Tree is a hierarchical structure. It means that the vertices of a tree could be divided into many sets which corresponds to vertices in some level. So we can define So=icc is the root) and Sk=bE tI there is aa E Sk and b is a immediate successor of a. For every k, Sk is finite and no Sk is empty because of infinity of given tree. Denote Pa as that vertex a is in path P. We now represent a tree with a set of propositions, 2,as following 1. VaESk Pa: there is at least one vertex of level k in a path 2. Va bes,-(pa A pb): there is only one vertex of level k in path p 3. Pa, Pb: b is a immediate successor of a3. ¬(pa,i ∧ pb,i), i = 1, . . . , k for all aEb. It means no neighbors have the same color . Then we get a set S with infinite propositions. For any finite subset S0 ⊂ X, we can extract vertices V0 from it and construct a set S1 which describe the graph G0 generated by V0. For every finite subgraph is k-colorable, S1 is satisfiable. S0 must be satisfiable. According to compactness theorem, S is satisfiable which means the graph is k-colorable. Remark: Generally, this theorem is not easy to prove via graph approach. Because there is no effective way to find it possible that a big graph is still k-colorable merged by two k-colorable graph. However, Compactness Theorem does not need this requirement. Here, we should be aware that a set of propositions is constructed and we try to prove that every finite subset of it is satisfiable, which is the essence of Compactness Theorem. Example 6. Every set S can be (totally) ordered. Similarly, it can be proved like k-colorable infinite graph. The point is to represent our problem with a set of propositions. This is left as an exercise. Hints: A set is partial order at least. If you can change a partially ordered set into a linear order set, you successfully complete the proof. 9 K¨onig Lemma and Compactness Theorem In our textbook, Compactness Theorem is proved by K¨onig lemma. Now we will show you that it can be proved by Compactness Theorem. Lemma 11 (K¨onig). A infinite tree with finite branch has a infinite path. Actually, the problem can be represented as following. If every a ∈ T has only finitely many immediate successor and T contains arbitrarily long finite paths, then there is a infinite path in T starts at root. Proof. Tree is a hierarchical structure. It means that the vertices of a tree could be divided into many sets which corresponds to vertices in some level. So we can define S0 = {c|c is the root} and Sk = {b ∈ T| there is a a ∈ Sk and b is a immediate successor of a}. For every k, Sk is finite and no Sk is empty because of infinity of given tree. Denote pa as that vertex a is in path P. We now represent a tree with a set of propositions, Σ, as following: 1. ∨a∈Sk pa: there is at least one vertex of level k in a path; 2. ∨a,b∈Sk¬(pa ∧ pb): there is only one vertex of level k in path p. 3. pa → pb: b is a immediate successor of a. 6