Изменения

Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936 года, Иштваном Фари (István Fáry) в 1948ом году и Штейном ( S. K. Stein) в 1951ом году. Поэтому иногда ее называют теоремой Фари-Вагнера.

|definition='''Триангуляция графа ''' {{---}} представление графа на плоскости в таком виде, что каждая его грань ограничена тремя ребрами (является треугольником).

|definition='''Разделяющий треугольник ''' {{---}} цикл длины <tex>3</tex> в графе <tex>G</tex>, внутри и снаружи которого находятся вершины графа.

Разделяющий треугольник изображён ниже. Относительно него существует три вида вершин: внешние, внутренние и лежащие на самом треугольнике.

|statement=Любой планарный граф имеет плоское представление на плоскости, в котором все его ребра будут прямымипредставлены в виде отрезков прямых.

Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G</tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>V</tex>. Предположим, что графы с числом вершин, меньшим <tex>V</tex>, мы можем нарисовать требуемым образом.

Рассмотрим ребро Предположим, что графы с числом вершин, меньшим <tex>vwV</tex>, мы можем нарисовать требуемым образом. Если в Рассмотрим ребро <tex>Gvw</tex> , инцидентное внутренней вершине глубочайшего разделяющего треугольника. Если в графе нет разделяющих треугольников, то <tex>vw</tex> {{---}} возьмём любое. Иначе <tex>vw</tex> {{---}} ребро, инцидентное вершине, находящейся внутри самого глубокого разделяющего треуголька в <tex>G</tex>. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.