Warning: this proof requires a bit of familiarity with the terminology of propositional logic and graph theory.

Problem: Let $G$ be an infinite graph. Show that $G$ is $n$-colorable if and only if every finite subgraph $G_0 \subset G$ is $n$-colorable.

Solution: One of the many equivalent versions of the Compactness Theorem for the propositional calculus states that if $\Sigma \subset \textup{Prop}(A)$, where $A$ is a set of propositional atoms, then $\Sigma$ is satisfiable if and only if any finite subset of $\Sigma$ is satisfiable. (Recall that a set of propositions is satisfiable if for some truth valuation $t:A \to \left \{ 0,1 \right \}$ the unique extension $\hat{t}:\Sigma \to \left \{ 0,1 \right \}$ satisfies $\hat{t}(p) = 1$ for all $p \in \Sigma$. The function $t$ is called a model for $\Sigma$). This is equivalent to the Completeness Theorem, which says that if one can use $\Sigma$ to prove $p$, then every model of $\Sigma$ satisfies $\hat{t}(p) = 1$. Both are fundamental results in logic.

And so we will convert this graph coloring problem into a logical set of propositions, and use the Compactness Theorem against it. We want a set of propositions $\Sigma$ which has a model if and only if the corresponding graph is n-colorable. Then we will use the n-colorability of finite subgraphs, to show that all finite subsets of $\Sigma$ have models, and this implies by the compactness theorem that $\Sigma$ has a model, so the original infinite graph is n-colorable.

We may think of a coloring of a graph $G$ as a function on the set of vertices: $c:V \to \left \{ 1, 2, \dots, n \right \}$. Define our set of propositional atoms as $A = V \times \left \{ 1, 2, \dots, n \right \}$. In other words, we identify a proposition $p_{v,i}$ to each vertex and possible color. So we will define three sets of propositions using these atoms, which codify the conditions of a valid coloring:

• $\left \{ p_{v,1} \vee p_{v,2} \vee \dots \vee p_{v,n} : v \in V \right \}$ i.e. every vertex must have some color,
• $\left \{ \lnot (p_{v,i} \wedge p_{v,j}) : i,j = 1, \dots, n, i \neq j, v \in V \right \}$ i.e. no vertex may have two colors, and
• $\left \{ \lnot (p_{v,i} \wedge p_{w,i}) : \textup{whenever } (v,w) \textup{ is an edge in } G \right \}$ i.e. no two adjacent vertices may have the same color.

Let $\Sigma$ be the union of the above three sets. Take $\Sigma_0 \subset \Sigma$ to be any finite set of the above propositions. Let $V_0$ be the finite subset of vertices of $G$ which are involved in some proposition of $\Sigma_0$ (i.e., $p_{v,i} \in \Sigma_0$ if and only if $v \in V_0$). Since every proposition involves finitely many atoms, $V_0$ is finite, and hence the subgraph of vertices of $V_0$ is n-colorable, with some coloring $c: V_0 \to \left \{ 1, 2, \dots, n \right \}$. We claim that this $c$ induces a model on $\Sigma_0$.

Define a valuation $t:A \to \left \{ 0,1 \right \}$ as follows. If $v \notin V_0$, then we (arbitrarily) choose $t(p_{v,i}) = 1$. If $v \in V_0$ and $c(v) = i$ then $t(p_{v,1}) = 1$. Finally, if $v \in V_0$ and $c(v) \neq i$ then $t(p_{v,i} = 0)$.

Clearly each of the possible propositions in the above three sets is true under the extension $\hat{t}$, and so $\Sigma_0$ has a model. Since $\Sigma_0$ was arbitrary, $\Sigma$ is finitely satisfiable. So by the Compactness Theorem, $\Sigma$ is satisfiable, and any model $s$ for $\Sigma$ gives a valid graph coloring, simply by choosing $i$ such that the proposition $p_{v,i}$ satisfies $s(p_{v,i}) = 1$. Our construction forces that such a proposition exists, and hence $G$ is n-colorable. $_\square$.

Note that without translating this into a logical system, we would be left with the mess of combining n-colorable finite graphs into larger n-colorable finite graphs. The number of cases we imagine encountering are mind-boggling. Indeed, there is probably a not-so-awkward graph theoretical approach to this problem, but this proof exemplifies the elegance that occurs when two different fields of math interact.

Want to respond? Send me an email or find me elsewhere on the internet.