57
правок
Изменения
Нет описания правки
Теорема была независимо доказана Клаусом Вагнером (Klaus Wagner) в 1936 года, 1936ом году и Иштваном Фари (István Fáry) в 1948ом году и Штейном ( S. K. Stein) в 1951ом году. Поэтому иногда Иногда ее называют теоремой Фари-Вагнера.
{{Определение
Переход: <tex>V \geqslant 4</tex>
Предположим, что графы с числом вершин, меньшим <tex>V</tex>, мы можем нарисовать требуемым образом.
Рассмотрим ребро <tex>vw</tex>, инцидентное внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.
[[File:Fary2.png|250px|Рисунок 2]]
Если <tex>vw</tex> не в разделяющем треугольнике <tex>p</tex> и <tex>q</tex> {{---}} любые общие соседи <tex>v</tex> и <tex>w</tex>.
Пусть <tex>(vp, vw, vq, vx_1, vx_2 ... vx_k)</tex> и <tex>(wq, wv, wp, wy_1, wy_2 ... wy_m)</tex> – обход по часовой стрелке ребер, исходящих соостветсвенно из <tex>v</tex> и <tex>w</tex>.
Пусть <tex>G'</tex> {{---}} планарная триангуляцияграф, полученная полученный из <tex>G </tex> стягиванием ребра <tex>vw</tex> в вершину <tex>s</tex>. Заменим пары параллельных ребер <tex>vq</tex> и <tex>wq</tex> на <tex>sq</tex> и <tex>vp, wp</tex> на <tex>sp</tex>. Получим вершину <tex>s</tex>, из которой исходят ребра <tex>(sp, sy_1, sy_2 ... sy_m, sq, sx_1, sx_2 ... sx_k)</tex> {{---}} по часовой стрелке.
[[File:Fary3.png|250px|Рисунок 3]]
