WikiSort.ru - Не сортированное

Утверждение

Если связный граф ${\displaystyle G}$ не изоморфен ни ${\displaystyle K_{5}}$ , ни ${\displaystyle K_{3,3}}$ , и для любого ребра ${\displaystyle e}$ графа ${\displaystyle G}$ оба графа ${\displaystyle G-e}$ и ${\displaystyle G/e}$ планарны, то ${\displaystyle G}$ планарен.

Лемма о графах Куратовского

Для произвольного графа ${\displaystyle K}$ следующие три условия равносильны:

1. Для любого ребра xy графа ${\displaystyle K}$ граф ${\displaystyle K-x-y}$ не содержит θ-графа, и из каждой вершины графа ${\displaystyle K-x-y}$ выходит не менее двух ребер.
2. Для любого ребра xy графа ${\displaystyle K}$ граф ${\displaystyle K-x-y}$ является циклом (содержащим ${\displaystyle n\geq 3}$ вершин).
3. ${\displaystyle K}$ изоморфен ${\displaystyle K_{5}}$ или ${\displaystyle K_{3,3}}$ .

Доказательство утверждения

Так как ${\displaystyle G}$ не изоморфен ни ${\displaystyle K_{5}}$ , ни ${\displaystyle K_{3,3}}$ , то по лемме о графах Куратовского существует ребро ${\displaystyle e=(xy)}$ графа ${\displaystyle G}$ , для которого в графе ${\displaystyle G-x-y}$ найдется либо вершина степени меньше 2 (в ${\displaystyle G-x-y}$ ), либо θ-подграф.

Если в графе ${\displaystyle G}$ из некоторой вершины выходит одно или два его ребра, то при стягивании одного из них получается планарный граф, значит, и граф G планарен. Поэтому далее будем считать, что из каждой вершины графа G выходит не менее трех его ребер.

Поэтому в графе ${\displaystyle G-x-y}$ нет изолированных вершин, и если есть висячая вершина p, то она соединена и с x, и с y в графе ${\displaystyle G}$ . Нарисуем граф ${\displaystyle G-(xy)}$ на плоскости без самопересечений. Так как в графе ${\displaystyle G}$ из p выходит три ребра, то 'с одной стороны' от пути xpy из p не выходит ребер. 'Подрисуем' ребро xy вдоль пути xpy 'с этой стороны' от него. Получим изображение графа G на плоскости без самопересечений.

Рассмотрим теперь случай, когда в графе ${\displaystyle G-x-y}$ найдется θ-подграф.

Из теоремы Жордана следует, что любой плоский граф разбивает плоскость на конечное число связных частей. Эти части называются гранями плоского графа.

Нарисуем без самопересечений на плоскости граф ${\displaystyle G/xy}$ . Изображение графа ${\displaystyle G-x-y=G/xy-xy}$ на плоскости получается стиранием ребер графа ${\displaystyle G/xy}$ , выходящих из вершины xy. Обозначим через ${\displaystyle {\bar {C}}}$ границу той грани (изображения) графа ${\displaystyle G/xy-xy}$ , которая содержит вершину xy графа ${\displaystyle G/xy}$ .

Заметим, что граница грани не может содержать θ-подграфа.

(Это утверждение можно вывести из теоремы Жордана. Другое доказательство получается от противного: если граница грани содержит θ-подграф, то возьмем точку внутри этой грани и соединим ее тремя ребрами с тремя точками на трех 'дугах' θ-подграфа. Получим изображение графа ${\displaystyle K_{3,3}}$ на плоскости без самопересечений. Противоречие.)

Поэтому ${\displaystyle G-x-y\neq {\bar {C}}}$ . Тогда ребра графа ${\displaystyle G-x-y-{\bar {C}}}$ находятся в грани (изображения) графа ${\displaystyle G-x-y=G/xy-xy}$ , не содержащей вершины xy. Значит, граф ${\displaystyle {\bar {C}}}$ разбивает плоскость. Поэтому найдется цикл ${\displaystyle C\subset {\bar {C}}}$ , относительно которого вершина xy лежит (не уменьшая общности) внутри, а некоторое ребро графа ${\displaystyle G-x-y-{\bar {C}}}$ — вне.

Обозначим через ${\displaystyle R}$ объединение всех ребер графа ${\displaystyle G/xy}$ , лежащих вне цикла ${\displaystyle C}$ . (Возможно,${\displaystyle G-x-y-{\bar {C}}\neq R}$ .) Можно считать, что ${\displaystyle R}$ — подграф в ${\displaystyle G}$ (а не только в ${\displaystyle G-x-y}$ ).

Граф ${\displaystyle G-R}$ можно нарисовать на плоскости без самопересечений. Можно считать, что ребра графа G, выходящие из x или y, на изображении графа ${\displaystyle G-R}$ лежат внутри цикла ${\displaystyle C}$ .

Каждая компонента связности графа ${\displaystyle G-x-y-R-C}$ пересекается с ${\displaystyle C}$ не более чем по одной точке.

(Если это не так, то в ${\displaystyle G-x-y-R-C}$ есть путь, соединяющий две точки на ${\displaystyle C}$ . На изображении графа ${\displaystyle G/xy}$ соответствующий путь лежит внутри цикла ${\displaystyle C}$ . Значит, этот путь разбивает внутреннюю часть цикла ${\displaystyle C}$ на две части, одна из которых содержит xy, a другая не лежит в грани, ограниченной ${\displaystyle {\bar {C}}}$ . Поэтому ${\displaystyle C\nsubseteq {\bar {C}}}$ — противоречие.)

Поэтому можно перекинуть внутрь цикла ${\displaystyle C}$ каждую компоненту связности графа ${\displaystyle G-x-y-R-C}$ . Значит, граф ${\displaystyle G-R-C}$ можно нарисовать внутри цикла ${\displaystyle C}$ . Нарисуем ${\displaystyle R}$ вне ${\displaystyle C}$ , как для изображения графа ${\displaystyle G/xy}$ . Получим изображение графа ${\displaystyle G}$ на плоскости без самопересечений.