57
правок
Изменения
Нет описания правки
[[File:Fary1.png|thumb|250px|Рисунок 1]]
Теорема была независимо доказана Клаусом Вагнером в 1936 года, Иштваном Фари в 1948ом году и Штейном в 1951ом году.
}}
Разделяющий треугольник представлен на рисунке 1. [[File:Fary1.png|thumb|500px|Рисунок 1]]
|statement= Любой планарный граф имеет представление на плоскости, в котором все его ребра будут прямыми.
|proof=
[[File:Fary2.png|thumb|250px|Рисунок 2]]
Докажем теорему для плоской триангуляции графа G. Ее можно достичь, добавив в G необходимое количество ребер. Применим индукцию по числу вершин V(G). Предположим, что графы с числом вершин, меньшим V, мы можем нарисовать требуемым образом.
База: V=3 — тривиально
Переход: V>=4
Рассмотрим ребро vw. Если в G нет разделяющих треугольников, то vw – любое. Иначе vw – ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в G. Тогда vw – граница двух граней vwp & vwq.
Если vw не в разделяющем треугольнике p & q – любые общие соседи v и w.
