Принцип крайнего, индукция и другие методы в комбигео

Индукция по База понятна: попарно не пересекающихся квадрата красим в один цвет, каждый из оставшихся квадратов — в свой цвет, всего использовано цветов. Теперь считаем, что и утверждение доказано для квадратов. Стороны квадратов считаем вертикальными и горизонтальными. Рассмотрим самый высокий (один из них) квадрат Если пересекается не более чем с другими квадратами,отбросим его мысленно, покрасим оставшиеся квадратов, пользуясь индукционным предположением, и докрасим Пусть — два нижних угла квадрата Заметим, что любой квадрат, пересекающий содержит точку или Предположим, что нашлось квадратов, пересекающих Добавим к этим квадратам и к произвольный квадрат Из этих квадратов каждый, кроме содержит точку или так что из них не выбрать попарно не пересекающихся — противоречие. Осталось рассмотреть случай, когда имеется ровно квадратов, пересекающих Добавим к ним и к любые два квадрата В полученном семействе все квадраты, кроме и содержат или поэтому два из попарно не пересекающихся квадратов в этом семействе — это обязательно и а ещё два — какие-то квадраты пересекающие (но отличные от В этом случае любые два квадрата, не пересекающие не пересекаются. Значит, можно покрасить в один цвет квадрат и все квадраты, не пересекающие в один цвет и остаётся всего квадрата — красим каждый в свой цвет.