Lesson 9

The previous proof is incorrect. It should be concerning that it does not use the fact that we do not have an arbitrary map, but a rather special one (all regions are obtained as a result of straight-line cuts). For example, the map below is not such (there are rays, not straight lines!) and cannot be colored with two colors.

To prove the required statement rigorously, we will, of course, use the method of mathematical induction. We prove by induction on the number of lines \(n\). The base case \(n=1\) is easily verified, so we proceed to the induction step \(n \to n+1\). So, we have a plane divided into parts by \(n\) lines, all parts are properly colored in two colors, and we draw a new line. On one side of this line, we change the colors of all parts. We will show that the resulting coloring is correct. If two parts are adjacent along a segment of one of the old lines, then they are of different colors by the induction hypothesis. And if they are adjacent along a segment of the new line, then they are of different colors because we recolored everything on one side.