Circles and Coloring

Several circles are drawn on a piece of paper to form several regions on the paper. We wish to color these regions such that no two regions that share a common boundary would have the same color.

(It is okay if two regions that share a common point to have the same color, but not boundary)

How many colors minimum are needed?

Solution

Two colors are sufficient.

For each circle $C$, we give a region the score of 1 if it's inside $C$ and 0 if it's outside of $C$. We go through the circles one by one and give scores accordingly, and at the end, we tally up the total scores of each region. If a region has an even score, we color it Red, and if it has an odd score, we color it Blue.

If two regions share a common boundary, that boundary must belong to a circle. One region would have to be inside that circle and another region outside. Their inside/outside-ness are identical with regard to all the other circles. Therefore, their scores differ by exactly 1, and they would have opposite color.