Color regions generated by circles with one chord (Induction)

Question

I am trying to learn Algorithms by reading the book Introduction to Algorithms: A Creative Approach by Udi Manber. I just want to solve this question:

Prove (by induction) that regions formed by $n$ circles in the plane, each with one chord,can be colored with three colors such that any neighboring regions are colored differently.

My guess is that when adding the new circle with its chord, we should start coloring the regions that have a neighbor colored. In other words, we should first color the regions with the lowest number of available colors. However, I cannot prove that in this way, we can color all regions.

Answer 1

Firstly let's prove that for circles without chords $2$ colors would be enough.

• The base of induction is an empty plane, $n = 0$. It needs $1$ color only, so it is $2$-colorable.

• When we add a circle, we can invert colors of all inner regions. Now there is no new problem with colors inside the circle, and outside of the circle. Also there is no new problem on the border, because for every region subdivided by the circle one part has the first color, while the other part has the second color. So if every pair of neighboring regions has different colors before adding the last circle, then after adding the last circle, every pair of neighboring regions still has different colors.

In the same way we can consider the problem about circles with chords. (And also we could do it similarly for any harder elements.)

• The base of induction is still an empty plane, $n = 0$. It needs $1$ color only, so it is $3$-colorable.

• When we add a circle with a chord, we can do the following. In one part inside the circle we change color of each subregion to the next one (the first to the second, the second to the third and the third to the first), while in the other part we change color of each subregion to the previous one (the first to the third, the second to the first and the third to the second). Then inside of each of three big regions (out of the circle, in one part of the circle and in the other part of the circle) no problem appears. At the same time no problem appears on the border, because for each region subdivided by the new circle each of any two neighboring parts get different new colors. Therefore if every pair of neighboring regions has different colors before adding the last circle, then after adding the last circle, every pair of neighboring regions still has different colors.