Изменения

Итак пусть граф <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>).

Пусть утверждение верно для <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>|V(T\backslash \{u\})| = |VT| - 1 = m - 1 < m</tex>.