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

**Problem**: Let be an infinite graph. Show that is -colorable if and only if every finite subgraph is -colorable.

**Solution**: One of the many equivalent versions of the Compactness Theorem for the propositional calculus states that if , where is a set of propositional atoms, then is satisfiable if and only if any finite subset of is satisfiable. (Recall that a set of propositions is satisfiable if for some truth valuation the unique extension satisfies for all . The function is called a *model* for ). This is equivalent to the Completeness Theorem, which says that if one can use to prove , then every model of satisfies . 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 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 have models, and this implies by the compactness theorem that has a model, so the original infinite graph is n-colorable.

We may think of a coloring of a graph as a function on the set of vertices: . Define our set of propositional atoms as . In other words, we identify a proposition 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:

- i.e. every vertex must have some color,
- i.e. no vertex may have two colors, and
- i.e. no two adjacent vertices may have the same color.

Let be the union of the above three sets. Take to be any finite set of the above propositions. Let be the finite subset of vertices of which are involved in some proposition of (i.e., if and only if ). Since every proposition involves finitely many atoms, is finite, and hence the subgraph of vertices of is n-colorable, with some coloring . We claim that this induces a model on .

Define a valuation as follows. If , then we (arbitrarily) choose . If and then . Finally, if and then .

Clearly each of the possible propositions in the above three sets is true under the extension , and so has a model. Since was arbitrary, is finitely satisfiable. So by the Compactness Theorem, is satisfiable, and any model for gives a valid graph coloring, simply by choosing such that the proposition satisfies . Our construction forces that such a proposition exists, and hence is n-colorable. .

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.

FYI: One of your latex formulas is borked.

LikeLike

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!

LikeLike

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.

LikeLike

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.

LikeLike