# Prove by induction that a circle cut by $n$ chords can be filled by 2 colors in a way that adjacent regions differ in color

Problem from How to Prove It: A Structured Approach.

Let $n \in N$ and suppose that $n$ chords are drawn in a circle, cutting the circle into a number of regions. Prove that the regions can be colored with two colors in such a way that adjacent regions (that is, regions that share an edge) are different colors.

Case $n=4$: Is the following proof enough?: Base case is simple and for the induction step suppose we have a circle cut by $n$ chords. Then it can be colored by 2 colors in the way mentioned above.

If we add another chord it cuts the circle in two parts. Both parts by itself must meet the coloring criteria. Let's leave one part's colors alone and consider changing colors only in the other part. Its regions that are incorrectly colored are the ones separated by the new chord. For each of these regions we have to change the color. But we can accomplish this just by switching the color of each region in the second part (the colors are arbitrary so it doesn't matter).

Now since both parts by itself are colored correctly and the regions separated by the new chord are also colored correctly the proof is done.

• Looks good, except I would write "mentioned below" rather than "mentioned above", and would be a little more explicit about the base case. (It's either $n=0$ or $n=1$ depending on your definition of $\mathbb N$.) – David K Sep 18 '16 at 13:25