Планарные графы

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

База: — очевидно.

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

_________________________________________________________________________________________________________________________________________________________________________________

Следствие. Внутри любого пятиугольника есть точка, из которой "видно"все точки этого пятиугольника.

Доказательство. Используя лемму выше, мы можем его триангулировать и правильно раскрасить в три цвета. Заметим, что вершина какого-то цвета будет всего одна. Тогда рассмотрим точку, которая очень близка к этой вершине, и она подойдет под условие.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к доказательству. Будем считать, что наш граф связный. Добавим в него ребра так, чтоб каждая его грань была треугольником (Для этого достаточно рассмотреть максимальный планарный граф). После укладки эти ребра мы удалим. Теперь сделаем индукцию по количеству вершин.

База: представляется треугольником.

Переход: Так как граф планарный найдется вершина степени Докажем, что существует такая вершина, не лежащая на границе внешней грани. Пусть не так. Тогда степень каждой вершины, не лежащей на границе внешней грани степень хотя бы При этом внешняя грань является треугольником. Степень каждой вершины на границе внешней грани хотя бы но у одной из вершин она будет хотя бы иначе весь граф является треугольником. Тогда сумма степеней вершин хотя бы

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