Теорема Понтрягина — Куратовского

Свойство 'граф ${\displaystyle G}$ содержит подграф, гомеоморфный графу ${\displaystyle H}$' будем сокращенно записывать в виде '${\displaystyle G\supset H}$'. Удаление ребра '${\displaystyle G-e}$', стягивание ребра '${\displaystyle G/e}$' и удаление вершины '${\displaystyle G-x}$'.

Достаточность в теореме Куратовского доказывается индукцией по количеству ребер в графе. Шаг индукции следует из Утверждения, поскольку если ${\displaystyle G-e\supset K_{5}}$ или ${\displaystyle G-e\supset K_{3,3}}$ или ${\displaystyle G/e\supset K_{5}}$ или ${\displaystyle G/e\supset K_{3,3}}$ для некоторого ребра e графа ${\displaystyle G}$, то ${\displaystyle G\supset K_{5}}$ или ${\displaystyle G\supset K_{3,3}}$. ‘Для ${\displaystyle G-e}$’ утверждение очевидно. Если ${\displaystyle G/xy\supset K_{3,3}}$, то ${\displaystyle G\supset K_{3,3}}$, а если ${\displaystyle G/xy\supset K_{5}}$, то ${\displaystyle G\supset K_{5}}$ или ${\displaystyle G\supset K_{3,3}}$.

Если связный граф ${\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}$ на плоскости без самопересечений.