## Coloring of an infinite map: inductive solution

https://bbzippo.wordpress.com/2011/01/18/coloring-of-an-infinite-map/

Assume that any **finite** map on the plane can be colored using 4 colors. Prove that **any** map on the plane can be colored using 4 colors.

**Proof**

*Definitions:*

Let’s call a proper coloring of a set S **extendable** if for any finite set E it can be extended to S U E.

If a coloring is not extendable then there exists a finite set D (a **“dead end” set**) such that our coloring can not be extended to S U D.

*Inductive Step Lemma:*

Let C be an extendable coloring of a set S. Let r be a single region. There exists an **extendable extension **of C to S U {r}.

*Proof of the Lemma:*

C has at most 4 extensions to S U {r}. Assume none of them is extendable. So each of them has a dead end set on which it can’t be extended. The union of those dead ends would be a dead end for C, so C would not be extendable. *QED.*

“Any finite map can be properly colored” basically means that **the coloring of the empty set is extendable**.

Let’s number our regions: r_1, r_2, …. Let R_n be the set of the first n regions. The coloring of the empty set extends to R_1. And by the lemma, it extends to all R_n. The union of all these extensions gives us a coloring of the whole map.

CONTINUE READING:

https://bbzippo.wordpress.com/2011/01/21/coloring-of-an-infinite-map-proof-by-compactness/

[…] https://bbzippo.wordpress.com/2011/01/20/coloring-of-an-infinite-map-inductive-solution/ […]

Coloring of an infinite map: Proof by compactness « Drawing Blanks01/21/2011 at 6:14 am