Mondrian Four-Coloring

generate cycle set

C

1

1

map of rectangles

200

four-coloring

2-color Hamiltonian cycle

second cycle set

squares

rectangles

Any planar map can be colored with four colors so that no two regions of the same color touch each other.

This Demonstration uses the following method to four-color each map:

1. A map of rectangles is converted to a cubic graph (not shown).

2. Cycle set

C

1

is a non-unique Hamiltonian cycle. Color its edges with two colors.

3. Eliminate one color of

C

1

and color the edges that are not in

C

1

in a third color. The result is a cycle set

C

2

in two colors.

4.

C

1

and

C

2

form the boundaries of two regions

R

1

and

R

2

.

5. Four cases leads to four possible colors for a rectangle, according to whether it is inside or outside

R

1

or

R

2

.

The method does not always work, since some cubic graphs exist that are not Hamiltonian. They are still four-colorable, but not by this method.