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

Докажем индукцией по что в хорошей раскраске нет четырёхугольника, в котором соседние вершины имеют противоположные цвета (будем называть такой четырёхугольник гадким).

База для очевидна. Теперь докажем переход от к Пусть в хорошей раскраске на вершинах есть гадкий четырёхугольник причём, не умаляя общности, вершины и — чёрные, а и — белые. Рассмотрим одну из триангуляций, которая соответсвует данной раскраске.

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

Если же вершина соединена ребром не со своим соседом — белой вершиной (не умаляя общности, вершины идут так: ---- то в одном из многоугольников, на которые делит ребро исходный многоугольник, есть гадкий четырёхугольник но раскраска при этом должна остаться правильной. По предположению индукции получаем противоречие.

Теперь разобьём многоугольник на блоки подряд идущих вершин одинакового цвета. По вышедоказанному блоков не больше 2 (иначе найдётся гадкий четырёхугольник), но одного блока быть не может, так как оба цвета, очевидно, присутствуют. Тогда блоков всего 2 и таких раскрасок

(выбрать начало чёрного блока — способов, а после этого белого — способ).

Заметим, что все такие раскраски подходят, а значит, всего существует хороших раскрасок.