Drawing Blanks

Premature Optimization is a Prerequisite for Success

Coloring of an infinite map: Proof by compactness

leave a comment »



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.


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.




Written by bbzippo

01/21/2011 at 6:14 am

Posted in math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: