# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Coloring of an infinite map: Proof by compactness

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

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

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

Let’s number the regions: r_1, r_2, …. Let’s number the colors: 0, 1, 2, 3.

For any n there exists a coloring of {r_1, r_2, …, r_n}. Let’s encode this coloring by a real number x_n with the decimal expansion 0.c1c2…cn where each digit is the number of the color of the corresponding region.

So we have an infinite sequence {x_n} of real numbers from [0, 1/3]. By compactness, it has at least one limit point X. Easy to see that X encodes a proper coloring of the whole map.

Notice that here (unlike in the inductive case) we didn’t bother to build a self-extending tower from ground up. The limit point is guaranteed to be such a tower. If it wasn’t, it wouldn’t be possible to find a proper coloring arbitrarily close to it.