Suppose finitely many possibly overlapping circles are drawn

Suppose finitely many, possibly overlapping, circles are drawn in the plane, dividing it into regions whose borders are made up of circular arcs. Shown that the regions can be coloured using white and black so that no two regions sharing a common border have the same colour.

Solution

We will argue by induction on the number of circles. For each natural number n, let Claim(n) be: ‘The regions created in the plane by n circles can be coloured with two colours.
’ Step 1. It is clear that the regions created by a single circle can be coloured with two colours, as there are only two regions. ( in the circle and outside it
Step 2. Let k be a natural number, and assume that Claim(k) is true, i.e., assume that the regions created in the plane by k circles can be coloured with two colours.
We wish to use this to prove Claim(k +1), i.e., that the regions created in the plane by k +1 circles can be coloured with two colours. Assume that we have k + 1 distinct circles in the plane. Choose any one of them, say l, and remove it. We are left with k circles, and so the resulting regions can be coloured with two colours, as we have assumed that Claim(k) is true.
Hence, there is a two-colouring of this set of regions. Take such a colouring of the regions, say with black and white, and add the circle l back. Change the colour of each region on one side of the circle ` (so black becomes white and white becomes black) and leave the regions on the other side of their original colour. (Consider two regions that share a border. There are two cases: either the border is part of the circle l or it is not. By the principle of mathematical induction, it follows that, for every natural number n, the regions created in the plane by n circles can be coloured with two colours.