Раскраска плоских графов (головоломка)

для прямых:

1) n=1. одна прямая делит карту на 2 части. двух красок достаточно
2) пусть n=k и карта раскрашена двумя красками
3) проводим k+1-ю прямую. она разделит карту на две (левую и правую) каждая из которых окрашена двумя красками. новая прямая проходит внутри окрашенных кусков поэтому слева и справа от нее цвет один (в пределах одного куска) . заменим в левой полукарте все цвета друг на друга (негатив) . получаем две полукарты окрашенные двумя цветами + слева и справа от новой прямой теперь разные цвета (в пределах старых кусков) . значит и с новой прямой раскраска в 2 краски возможна.

по матиндукции - доказано

для окружностей по аналогии
1) одна окружность - да (очевидно)
2) пусть верно для n=k
3) рисуем k+1-ю. инвертируем цвета всех кусков за пределами новой окружности (включительно с полукусками отрезанными новой окружностью) . получаем что все касающиеся окружности внешние куски по линии касания напротив имеют другой цвет.

тоже - доказано

Прямые:
Будем действовать так. Проводим первую прямую, она делит плоскость на две полуплоскости, каждую из которых красим разным цветом. Проводим вторую прямую и с одной стороны инвертируем окраску, а с другой - нет. И так далее. При таком построении, очевидно, соседние области всегда будут иметь разный окрас.