37
правок
Изменения
Нет описания правки
[[Файл:p-k.3.png|thumb|right|рис. 3]]
Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно.
<br/> <br/>
Пусть <tex> e = ab </tex> - произвольное ребро графа <tex> G </tex>, <tex> G' = G - e </tex>.
# граф <tex> G' </tex> планарен в силу минимальности графа <tex> G </tex>.
# граф <tex> G' </tex> связен в силу отсутствия в графе <tex> G </tex> мостов.
==== В G' существует цикл, содержащий вершины a и b ====
Пусть <tex> a </tex> и <tex> b </tex> лежат в одном блоке <tex> B </tex> графа <tex> G' </tex>.
# Если <tex> |VB| >= 3 </tex>, то существует цикл графа G', содержащий вершины <tex> a </tex> и <tex> b </tex>.
# Если <tex> |VB| = 2 </tex>, то в <tex> B </tex> имеется ребро <tex> e' = ab </tex>, но тогда в <tex> G </tex> имеются кратные рёбра <tex> e </tex> и <tex> e' </tex>, что невозможно.
# Если вершины <tex> a </tex> и <tex> b </tex> лежат в разных блоках графа <tex> G' </tex>, что существует точка сочленения <tex> v </tex>, принадлежащая любой простой (a, b)-цепи графа <tex> G' </tex>. Через <tex> G'_1 </tex> обозначим подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами компоненты связности графа <tex> G' - v </tex>, содержащей <tex> a </tex>, а через <tex> G'_2 </tex> - подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами остальных компонент связности графа <tEx> G' - v </tex> (в этом множестве лежит вершина <tex> b </tex>). Пусть <tex> G''_1 = G'_1 + e_1 </tex>, где <tex> e1 = vb </tex> - новое ребро (рис. 4)
[[Файл:p-k.4.png|thumb|right|рис. 4]]
Заметим, что в графе <tex> G''_1 </tex> рёбер меньше, чем в графе <tex> G </tex>. Действительно, вместо ребра <tex> e </tex> в <tex> G''_1 </tex> есть ребро <tex> e1 </tex> и часть рёбер из графа <tex> G </tex> осталась в графе <tex> G''_2 </tex>. Аналогично, в графе <tex> G''_2 </tex> рёбер меньше, чем в графе <tex> G </tex>. <br/>
Покажем, далее, что в графе <tex> G''_1 </tex> и, аналогично, в графе <tex> G''_2 </tex> нет подграфов, гомеоморфных <tex> K_5 </tex> или <tex> K_{3,3} </tex>. Действительно, если в <tex> G''_1 </tex> имеется такой подграф, то в этом подграфе присутствует вновь присоединенное ребро, но это ребро <tex> e1 </tex> можно заменить на цепь <br/>
a -> b -> ... -> v, <br/> взяв некоторую простую (b, v)-цепь <tex> P_2 </tex> в графе <tex> G'_2 </tex>. Следовательно, мы получили подграф в <tex> G </tex>, гомеоморфный <tex> К_5 </tex> или <tex> К_{3,3} </tex>, что невозможно. <br/>
Теперь в силу минимальности графа <tex> G </tex> графы <tex> G''_1 </tex> и <tex> G''_2 </tex> планарны. Возьмем укладку графа <tex> G''_1 </tex> на плоскости такую, что ребро <tex> е1 = av </tex> лежит на границе внешней грани. Во внешней грани графа <tex> G''_1 </tex> возьмем укладку графа <tex> G''_2 </tex> такую, что ребро <tex> е2 = vb </tex> лежит па границе внешпей грани (рис. 5).
[[Файл:p-k.5.png|thumb|right|рис. 5]]
Отметим, что опять вершина <tex> v </tex> представлена на плоскости в двух экземплярах. Очевидно, добавление ребра <tex> е = ab </tex> не меняет планарности графа <tex> G''_1 U G''_2</tex>. Склеим оба вхождения вершины <tex> v </tex> точно так же, как это мы сделали в предыдущем пункте доказательства (рис. 6).
[[Файл:p-k.6.png|thumb|right|рис. 6]]
Сотрем затем ранее добавленные ребра <tex> е1 </tex> и <tex> е2 </tex>. В результате мы получим укладку графа <tex> G </tex> на плоскости, что невозможно. Утверждение доказано.
