57
правок
Изменения
Нет описания правки
Докажем теорему для плоской триангуляции графа <tex>G</tex>. Ее можно достичь, добавив в <tex>G</tex> необходимое количество ребер. Применим индукцию по числу вершин <tex>V</tex>.
База: индукции, когда <tex>V=3</tex> {{---}} тривиально, выполняется тривиальным образом. Переход: <tex>V \geqslant 4</tex> Предположим, что графы с любым числом вершин, меньшим <tex>V\geqslant 4</tex>, мы можем нарисовать требуемым образом.
Рассмотрим ребро <tex>vw</tex>, инцидентное внутренней вершине глубочайшего разделяющего треугольника, то есть такого, который не содержит внутри себя других разделяющих треугольников. Если в графе нет разделяющих треугольников, то возьмём любое ребро. Тогда <tex>vw</tex> {{---}} граница двух граней <tex>vwp</tex> и <tex>vwq</tex>.
