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.