53
правки
Изменения
Нет описания правки
{{Теорема
|about=об укладке графа с планарными компонентами вершинной двусвязности
|statement=Если [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа ]] <tex>G</tex> [[Укладка графа на плоскости|планарны]], то и сам граф <tex>G</tex> планарен.
|proof=
}}
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge 1</tex> , а значит имеется по-крайней мере один блок в <tex>G</tex>. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, что <tex>\forall v</tex> — - т.с. <tex>G</tex> имеем <tex>deg(v) \ge 2</tex>. Из [[Граф блоков-точек сочленения#lemma1|леммы]] и из связности <tex>T</tex> - получаем, что <tex>T</tex> — двудольное [[Дерево, эквивалентные определения|дерево]].
Докажем индукцией по числу вершин в графе <tex>T</tex>, что подграф <tex>G'</tex> графа <tex>G</tex> состоящий из блоков графа <tex>G</tex> принадлежащих графу <tex>T</tex> планарен (далее будем говрить, что <tex>G'</tex> соответствует <tex>T</tex>).
