# Section 1.7: Problem 4 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
In 1977 it was proved that every planar map can be colored with four colors. Of course, the definition of “map” requires that there be only finitely many countries. But extending the concept, suppose we have an infinite (but countable) planar map with countries $C_{1},C_{2},C_{3},\ldots$ . Prove that this infinite planar map can still be colored with four colors. (Suggestion: Partition the sentence symbols into four parts. One sentence symbol, for example, can be used to translate, “Country $C_{7}$ is colored red.” Form a set $\Sigma_{1}$ of wffs that say, for example, $C_{7}$ is exactly one of the colors. Form another set $\Sigma_{2}$ of wffs that say, for each pair of adjacent countries, that they are not the same color. Apply compactness to $\Sigma_{1}\cup\Sigma_{2}$ .)
We need a set $\Sigma$ of wffs such that truth assignments that satisfy $\Sigma$ correspond one-to-one to “correct” colorings of the graph. So, let $A_{i,j}$ be the sentence symbol corresponding to the sentence “Country $C_{i}$ is colored using color $j$ ”, where $i\ge1$ and $j\in\{1,2,3,4\}$ . Then, first, we must ensure that every truth assignment satisfying $\Sigma$ colors each country into a single color. For this, we consider the set of wffs $\Sigma_{1}=\{B_{i}|i\in\mathbb{N}\}$ where $B_{i}=\A_{i,1}A_{i,2}A_{i,3}A_{i,4}$ and $\$ is a quaternary connective being true iff one exactly of its operands is true. Second, we must ensure that no two adjacent countries are colored the same color. For this, we consider the set of wffs $\Sigma_{2}=\{D_{i,j,k}|(i,k)\in R,j\in\{1,2,3,4\}\}$ where $R$ is the binary relation on the set of country indexes such that $(i,k)\in R$ iff countries $C_{i}$ and $C_{k}$ are adjacent, and $D_{i,j,k}=A_{i,j}|A_{k,j}$ ($C_{i}$ and $C_{k}$ cannot both be painted using color $j$ ). Let $\Sigma=\Sigma_{1}\cup\Sigma_{2}$ . Now, every truth assignment (every assignment of some colors for each country) that satisfies $\Sigma$ corresponds to a correct coloring (exactly one color is assigned to each country, and no two adjacent countries share the same color). And vice versa, every correct coloring assigns exactly one color to each country $C_{i}$ (satisfying $B_{i}$ ) and does not assign the same color $j$ to two adjacent countries $C_{i}$ and $C_{k}$ (satisfying $D_{i,j,k}$ ). Now, if we show that every finite subset of $\Sigma$ is satisfiable, we can apply the compactness theorem to conclude that $\Sigma$ is satisfiable and a correct coloring exists. So, let us show that every finite subset of $\Sigma$ is satisfiable. Let $\Sigma_{0}$ be a finite subset of $\Sigma$ . Let $S$ be the (finite) set of country indexes used in $\Sigma_{0}$ , i.e.
Now, we extend $\Sigma_{0}$ to $\Sigma'$ by including $B_{i}$ for all $i\in S$ , and $D_{i,j,k}$ and $D_{k,j,i}$ for all $i,k\in S$ such that $(i,k)\in R$ and $j\in\{1,2,3,4\}$ . The truth assignments that satisfy correspond one-to-one to correct colorings of the finite subgraph $G$ consisting of the countries with indexes in $S$ . Since $S$ is finite, $G$ is finite, and according to the 4-color theorem for finite graphs, there is a correct coloring of $G$ , i.e. $\Sigma'$ is satisfiable, and so is $\Sigma_{0}$ .