Exercise 21 (Vertex Coloring in Simple Graphs). All graphs G = (V, E) in this exercise are simple, finite or infinite. Once more, we take the set V of vertices as

an initial fragment of the positive integers {1,2,...}, finite or infinite, and its set of edges E CV X V. Such a graph G is said k-colorable if it is possible to assign only one of k colors to every vertex of G such that the two endpoints of every edge are assigned different colors. A famous (and very difficult to prove) result of graph theory is that every finite planar graph is 4-colorable. In this exercise you are asked to show that this result can be extended to infinite planar graphs using Compactness for PL. Let k> 1 be fixed, the number of available colors. For convenience, use two separate sets of propositional variables, Q and C, instead of P: def def {9₁.j|i,j€ {1,2,...}} and C f {ci € {1,2,...} and 1 ≤ j≤ k}. All wff's in this exercise should be in WFFPL (QUC). Use variables in Q to model a given graph G: there is an edge connecting two distinct vertices i and jiff qij is set to truth value true. Use variables in C to model G's coloring: vertex i is assigned color j = {1,...,k} iff is set to truth value true. There are three parts in this exercise, the first two are not limited to planar graphs: 1. Let G = (V, E) be a finite simple graph. Write a wff (G) which is satisfied iff G is k-colorable. Hint: Define (G) in two parts, one part specifies the structure of G (including conditions that there are no self-loops and that G is undirected), and one part specifies that G is k-colorable. You will find it useful to review Example 20. 2. Let Gf (V, E) be an infinite simple graph, with V = {1,2,...}. Show that G is k-colorable iff every finite subgraph of G is k-colorable. Hint: If an infinite G is k-colorable, then so is every finite subgraph of G. This is the easy implication. Compactness for PL should give you the converse, after writing an infinite set Þ(G) of wff's in WFFPL (QUC) expressing the k-colorability of G. 3. Let G = (V, E) be an infinite planar graph, with V = {1,2,...}. Invoke the preceding part to conclude that G is 4-colorable.