Изменения

Докажем индукцией по числу вершин в графе <tex>T</tex>, что подграф <tex>G'</tex> графа <tex>G</tex> состоящий из компонент реберной двусвязности и [[Мост,_эквивалентные_определения|мостов ]] графа <tex>G</tex> принадлежащих графу <tex>T</tex> планарен (далее будем говорить, что <tex>G'</tex> соответствует <tex>T</tex>).

Положим <tex>G_1</tex> &mdash; компонента реберной двусвязности графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>e</tex> &mdash; [[Мост,_эквивалентные_определения|мост ]] в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex> (рис. 3). <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> &mdash; висячая вершина <tex>T</tex>, то <tex>T\backslash \{G_1\}</tex> связен, и, очевидно, также как и <tex>T</tex> является подграфом графа компонент реберной двусвязности <tex>G</tex>. Итак <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>|V(T\backslash \{G_1\})| = |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>.