# n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof)

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.

## 4 thoughts on “n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof)”

1. Brian Oppenheim

FYI: One of your latex formulas is borked.

• j2kun

Yeah…”Simga” is not a greek letter recognized by latex. Thanks for that. Also: I didn’t know you read my blog, what a nice surprise!

• Brian Oppenheim

Yeah, two topics that I enjoy merged together. It’s definitely a great concept. The only frustrating part is that I’ve lost more knowledge than I’d like from my minor classes so I don’t usually get all of the details.

• j2kun

Well if you ever have a question on a particular detail, don’t hesitate to ask! Nobody really asks me for clarification so I assume I’m writing at the correct level.