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$:

enter image description here

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.

  • 1
    $\begingroup$ 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$.) $\endgroup$ – David K Sep 18 '16 at 13:25

This nice argument is correct. You might want to note that it works even if the new chord goes through a point at which two old chords intersect, just to save the reader the trouble of checking


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.