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.
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!
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.
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.