Coloring a map

Suppose the figure can be colored using three distinct colors from the set $\{A, B, C\}$ .

We arbitrarily choose $A$ for the center circle. Since each of the four regions of the second circle touches $A$ , we must alternately color them with the two remaining colors, $B$ and $C$ .

Now, the right outer region is connected to $B$ and $C$ , so it must be colored the remaining color $A$ . Similarly, the top outer region is connected to $C$ and $B$ , so it must also be colored $A$ . However, the top and right regions are connected, so both cannot be colored $A$ . This is a contradiction; hence, the figure requires more than three colors.

We now know three colors is not possible. So, use some fourth color $D$ and color the outer circle alternately $D$ , $A$ , $D$ , $A$ . Since this results in a valid four-color arrangement, it can be colored using four distinct colors .