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. $$\begin{eqnarray*} S & = & \{i\ge1|B_{i}\in\Sigma_{0}\mbox{ or there exist }j\in\{1,2,3,4\}\mbox{ and }\\ & & k\ge1\mbox{ such that }D_{i,j,k}\in\Sigma_{0}\mbox{ or }D_{k,j,i}\in\Sigma_{0}\}. \end{eqnarray*}$$

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 $\Sigma'$ 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}$ .