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

Твердження

Якщо зв'язний граф ${\displaystyle G}$ не ізоморфний ні ${\displaystyle K_{5}}$, ні ${\displaystyle K_{3,3}}$, і для будь-якого ребра ${\displaystyle e}$ графу ${\displaystyle G}$ обидва графи ${\displaystyle G-e}$ і ${\displaystyle G/e}$ планарні, то ${\displaystyle G}$ — планарний.

Лема про графи Куратовського

Для довільного графу ${\displaystyle K}$ рівносильними є три такі умови:

1. Для будь-якого ребра ${\displaystyle xy}$ графу ${\displaystyle K}$ граф ${\displaystyle K-x-y}$ не містить θ-графу, і з кожної вершини графу ${\displaystyle K-x-y}$ виходить не менше двох ребер.
2. Для будь-якого ребра ${\displaystyle 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}$ з деякої вершини виходить одне або два його ребра, то при стягуванні одного з них виходить планарний граф, отже, і граф ${\displaystyle G}$ планарний. Тому далі будемо вважати, що з кожної вершини графу ${\displaystyle G}$ виходить не менше трьох його ребер.

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

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

З теореми Жордана випливає, що будь-який плоский граф розбиває площину на скінченне число зв'язних частин. Ці частини називаються гранями плоского графу.

Намалюємо без самоперетинів на площині граф ${\displaystyle G/xy}$. Зображення графу ${\displaystyle G-x-y=G/xy-xy}$ на площині отримуємо стиранням ребер графу ${\displaystyle G/xy}$, що виходять з вершини ${\displaystyle xy}$. Позначимо через ${\displaystyle {\bar {C}}}$ межу тієї грані (зображення) графу ${\displaystyle G/xy-xy}$, яка містить вершину графу ${\displaystyle 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}$, що не містить вершини ${\displaystyle xy}$. Отже, граф ${\displaystyle {\bar {C}}}$ розбиває площину. Тому знайдеться цикл ${\displaystyle C\subset {\bar {C}}}$ відносно якого вершина ${\displaystyle xy}$ лежить (не зменшуючи загальності) всередині, а деяке ребро графу ${\displaystyle C\subset {\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}$ можна намалювати на площині без самоперетинів. Можна вважати, що ребра графу ${\displaystyle G}$, що виходять з ${\displaystyle x}$ або ${\displaystyle 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}$ на дві частини, одна з яких містить ${\displaystyle 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}$ на площині без самоперетинів.