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

Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа. Имеет эквивалентную формулировку на языке миноров, так называемою теорему Вагнера.

Теорема утверждает, что графы K₅ (полный граф на 5 вершинах) и K_3,3 (полный двудольный граф имеющий по 3 вершины в каждой доле) являются единственными минимальными непланарными графами.

История

Была доказана в 1930 году польским математиком Казимиром Куратовским и в 1927 году советским математиком Львом Семёновичем Понтрягиным, который не опубликовал своё доказательство.

Предварительные определения

Граф называется планарным, если его можно изобразить на двумерной плоскости так, чтобы его ребра попарно не пересекались.

Граф $G'$ называется подразбиением графа $G$, если $G'$ можно получить из $G$ добавлением вершин на его рёбра.

Формулировка

Граф планарен тогда и только тогда, когда он не содержит подразделений полного графа с пятью вершинами (K₅) и полного двудольного графа с тремя вершинами в каждой доле (K_3,3).

Доказательство

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариации и обобщения

• Теорема Вагнера — другая формулировка теоремы Понтрягина — Куратовского, через миноры.
• Теорема Робертсона — Сеймура.

Ссылки

• А. Б. Скопенков. Вокруг критерия Куратовского планарности графов // Математическое просвещение сер. 3. — 2005. — Т. 9. — С. 116—128./arXiv:0802.3820
• Yu. Makarychev, A short proof of Kuratowski’s graph planarity criterion, J. of Graph Theory, 25 (1997) 129—131.