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

DevFeed: [n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof)](<https://devfeed.tech/articles/n-colorability-is-equivalent-to-finite-n-colorability-a-formal-logic-proof-40241.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/09/04/n-colorability-is-equivalent-to-finite-n-colorability/>)

Published: 2011-09-04T22:41:27Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [completeness](<https://devfeed.tech/tags/completeness.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [graph-theory](<https://devfeed.tech/tags/graph-theory.md>), [logic](<https://devfeed.tech/tags/logic.md>), [vertex](<https://devfeed.tech/tags/vertex.md>)

## AI overview

A formal logic proof shows that an infinite graph is n-colorable exactly when every finite subgraph is n-colorable. The proof encodes valid colorings as propositional formulas and applies the Compactness Theorem.

## Source excerpt

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.