Изменения

|statement=Граф <tex>G</tex> планарен тогда и только тогда , когда он обладает укладкой на сфере

Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex> , не лежащую на ребре , и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и при этом не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя всевозможные все возможные лучи из точки <tex>N</tex> через точки сферы до плоскостипересечения с плоскостью. Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости.

Сначала возьмем Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в [[#l1|лемме III]], за точку <tex>N</tex> возьмем точку на сфере , не лежащую на ребре, не являющуюся вершиной, и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством.

Докажем утверждение теоремы для одной из компонент связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности какого-либо графа , мы можем получить укладку на плоскости и всего графа.Итак пусть граф <tex>G</tex> связен. Рассмотрим связный подграф <tex>T</tex> графа к.р.д. графа <tex>G</tex>. Из [[Граф компонент реберной двусвязности|леммы]] и из связности <tex>T</tex> - получаем, что <tex>T</tex> - &mdash; [[Дерево, эквивалентные определения|дерево]].

Положим <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>. <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 \{u\})| = |VT| - 1 = m - 1 < m</tex>.

Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' (если таковое имеется) оказалось на границе внешней грани (по [[#l1l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит <tex>G_1</tex> тривиальный. В таком случае возьмем любую его укладку на плоскости. Обозначим за <tex>u</tex> вершину из <tex>G_2</tex> инцедентную <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex> , так , чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Проводя ребро Проведем жорднанову кривую, соответствующую ребру <tex>e</tex> , от вершины <tex>u</tex> к инцидентоной ему <tex>e</tex> вершине графа <tex>G_1</tex> мы получаем так, чтобы она не пересекалась с укладками <tex>G_1</tex> и <tex>G_2</tex>. Мы получили укладку графа <tex>G'</tex> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.