53
правки
Изменения
Нет описания правки
Докажем утверждение теоремы для одной из компоненты связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.
Итак пусть граф <tex>G</tex> - связен. Рассмотрим связный подграф <tex>T</tex> графа компонент реберной двусвязности графа <tex>G</tex>. Из [[Граф компонент реберной двусвязности|леммы]] и из связности <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>).
<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим дерево <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> подграф <tex>G'</tex> графа <tex>G</tex>. Докажем, что <tex>G'</tex> - планарен.
Положим <tex>G_1</tex> - блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>e</tex> - мост в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Далее рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Он Поскольку <tex>G_1</tex> - висячая вершина <tex>T</tex>, то <tex>T\backslash \{G_1\}</tex> связен, и очевидно также как и <tex>T</tex> является подграфом графа компонент реберной двусвязности <tex>G</tex>. А значит <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>|V(T\backslash \{u\})| = |VT| - 1 = m - 1 < m</tex>.
Из определения ребер дерева компонент реберной двусвязности получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> соединены в графе <tex>G'</tex> единственным мостом <tex>e \in G'</tex> инцидентным блоку <tex>G_1</tex> в дереве <tex>T</tex>. Поскольку <tex>T = \{G_1\}\cup e\cup \{G_2\}</tex>, то и <tex>G' = \{G_1\}\cup e\cup \{G_2\}</tex>. Покажем как из укладок <tex>G_1</tex> и <tex>G_2</tex> получить укладку <tex>G'</tex>.
