Lesson 8

The famous four color theorem states that the regions of any map can be properly colored with four colors so that adjacent regions (those with a common boundary of non-zero length) have different colors. Its proof is complex (and we still do not know a proof that does not involve computer enumeration!).

Problem. Consider a special case of this problem where all regions are formed by straight cuts.

The plane is divided into regions by several straight lines. Prove that the regions can be colored with two colors properly: so that adjacent regions are colored differently.

Is this a correct proof?

Color an arbitrary region with the first color. Color all regions adjacent to it with the second color. Color all their neighbors with the first color. And so on. Since the total number of regions is finite, we will eventually obtain a proper coloring.