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?
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.