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

Теорему доказал в 1927 году известный советский математик Лев Семенович Понтрягин, но не опубликовал. Независимо от Понтрягина в 1930 году доказательста нашел и впервые напечатал польский математик Казимир Куратовский. Первые доказательства теоремы Понтрягина-Куратовского были очень сложными. Сравнительно простое доказательство нашел в 1997 г. петербургский школьник Юрий Макарычев.

Теорема:

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных $K_{5}$ или $K_{3, 3}$ .

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

$\triangleright$

Заметим, что из планарности графа следует планарность гомеоморфного графа и наоборот. В самом деле, пусть $G_1$ — плоский граф. Если добавить на нужных ребрах вершины степени $2$ и удалить некотрые вершины степени $2$ в $G_1$, получим укладку гомеоморфного графа $G_2$. Таким образом, доказательство необходимости следует из непланарности $K_5$ и $K_{3, 3}$. Докажем достаточность. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных $K_{5}$ или $K_{3, 3}$. Пусть $G$ — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин. G связен Если $G$ не связен, то в силу минимальности $G$ его компоненты связности планарны и, следовательно, сам граф $G$ планарен. G — обыкновенный граф В самом деле, пусть в графе $G$ есть петля или кратное ребро $e$. Тогда в силу минимальности $G$ граф $G - e$ планарен. Добавляя ребро $e$ к графу $G - e$ получим, что граф $G$ планарен. G — блок Пусть, от противного, в графе есть точка сочленения $v$. Через $G_1$ обозначим подграф графа $G$, порождённый вершинами одной из компонент связности графа $G - v$ и вершинной $v$, а через $G_2$ подграф графа $G$, порождённый вершинами остальных компонент связности графа $G - v$ и вершиной $v$. В силу минимальности $G$, $G_1$ и $G_2$ — планарны. Возьмём укладку графа $G_1$ на плоскости такую, что вершина $v$ лежит на границе внешней грани. Ее можно получить, взяв любую укладку $G_1$ на плоскости, по ней построив укладку на шаре, используя обратную стереографическую проекцию, потом повернуть сферу так, чтоб $v$ оказалась на внешней грани стереографической проекции повернутого шара. Затем во внешней грани графа $G_1$ возьмём укладку графа $G_2$ такую, что вершина $v$ будет представлена на плоскости в двух экземплярах. Соединим два экземпляра вершины $v$ пучком жордановых линий, не допуская лишних пересечений с укладками графов $G_1$ и $G_2$, состоящим из такого количества линий, какова степень вершины $v$ в графе $G_2$. Далее отбросим вхождение вершины $v$ в граф $G_2$, заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер. Таким образом мы получили укладку графа $G$ на плоскости, что невозможно. В G нет мостов Граф $G$ не равен $K_2$ и в нем нет точек сочленения, следовательно в $G$ нет мостов. В G' существует цикл, содержащий вершины a и b Пусть $e = ab$ — произвольное ребро графа $G$, $G' = G - e$. граф $G'$ планарен в силу минимальности графа $G$. граф $G'$ связен в силу отсутствия в графе $G$ мостов. Пусть $a$ и $b$ лежат в одном блоке $B$ графа $G'$. Если $|VB| \geqslant 3$, то существует цикл графа G', содержащий вершины $a$ и $b$. Если $|VB| = 2$, то в $B$ имеется ребро $e' = ab$, но тогда в $G$ имеются кратные рёбра $e$ и $e'$, что невозможно. Если вершины $a$ и $b$ лежат в разных блоках графа $G'$, что существует точка сочленения $v$, принадлежащая любой простой $(a, b)$ — цепи графа $G'$. Через $G'_1$ обозначим подграф графа $G'$, порождённый вершиной $v$ и вершинами компоненты связности графа $G' - v$, содержащей $a$, а через $G'_2$ — подграф графа $G'$, порождённый вершиной $v$ и вершинами остальных компонент связности графа $G' - v$ (в этом множестве лежит вершина $b$). Пусть $G''_1 = G'_1 + e_1$, где $e_1 = vb$ — новое ребро. Заметим, что в графе $G''_1$ рёбер меньше, чем в графе $G$. Действительно, вместо ребра $e$ в $G''_1$ есть ребро $e_1$ и часть рёбер из графа $G$ осталась в графе $G''_2$. Аналогично, в графе $G''_2$ рёбер меньше, чем в графе $G$. Теперь в силу минимальности графа $G$ графы $G''_1$ и $G''_2$ планарны. Возьмем укладку графа $G''_1$ на плоскости такую, что ребро $e_1 = av$ лежит на границе внешней грани(ее существование доказывается аналогично существованию такой укладки для вершины графа). Во внешней грани графа $G''_1$ возьмем укладку графа $G''_2$ такую, что ребро $e_2 = vb$ лежит па границе внешней грани. Отметим, что опять вершина $v$ представлена на плоскости в двух экземплярах. Очевидно, добавление ребра $e = ab$ не меняет планарности графа $G''_1 U G''_2$. Склеим оба вхождения вершины $v$ точно так же, как это мы сделали в предыдущем пункте доказательства. Сотрем затем ранее добавленные ребра $e_1$ и $e_2$. В результате мы получим укладку графа $G$ на плоскости, что невозможно. Утверждение доказано. Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части Среди всех укладок графа $G'$ на плоскости и среди всех циклов $C$, содержащих $a$ и $b$, зафиксируем такую укладку и такой цикл, что внутри области, ограниченной циклом $C$, лежит максимальное возможное число граней графа $G'$. Зафиксируем один из обходов по циклу $C$ (на рисунках будем рассматривать обход по часовой стрелке по циклу $C$). Для вершин $u$ и $v$ цикла $C$ через $C[u,v]$ будем обозначать простую $(u,v)$ — цепь, идущую по циклу $C$ от $u$ до $v$ в направлении обхода цикла. Конечно, $C[u,v] \ne C[v,u]$. Положим $C(u,v) = C[u,v] \setminus$ {$u,v$}, т.е. $C(u,v)$ получено из $C[u,v]$ отбрасыванием вершин $u$ и $v$. Определение: Внешним графом (англ. Outside graph) (относительно цикла $C$) будем называть подграф графа $G'$, порождённый всеми вершинами графа $G'$, лежащими снаружи от цикла $C$. Определение: Внешними компонентами (англ. Outside components) будем называть компоненты связности внешнего графа. В силу связности графа $G'$ для любой внешней компоненты должны существовать рёбра в $G'$, соединяющие её с вершинами цикла $C$. Определение: Внешними частями (англ. Outside parts) будем называть внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла $C$, и инцидентными им вершинами , либо рёбра графа $G'$, лежащие снаружи от цикла $C$ и соединяющие две вершины из $C$, вместе с инцидентными такому ребру вершинами. Определение: Внутренним графом (англ. Inside graph) (относительно цикла $C$) будем называть подграф графа $G'$, порождённый всеми вершинами графа $G'$, лежащими внутри цикла $C$. Определение: Внутренними компонентами (англ. Inside components) будем называть компоненты связности внутреннего графа. В силу связности графа $G'$ для любой внутренней компоненты должны существовать рёбра в $G'$, соединяющие её с вершинами цикла $C$. Определение: Внутренними частями (англ. Inside parts) будем называть внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла $C$, и инцидентными им вершинами, либо рёбра графа $G'$, лежащие внутри цикла $C$ и соединяющие две вершины из $C$, вместе с инцидентными такому ребру вершинами Будем говорить, что внешняя (внутренняя) часть встречает цикл $C$ в своих точках прикрепления к циклу $C$. Лемма (1): Любая внешняя часть встречает цикл $C$ точно в двух точках, одна из которых лежит в $C(a,b)$, а другая — в $C(b,a)$. Доказательство: $\triangleright$ Если внешняя часть встречает цикл $C$ точно в одной точке $v$, то $v$ является точкой сочленения графа $G$, что невозможно. Таким образом, внешняя часть встречает цикл $C$ не менее чем в двух точках. Если внешняя часть встречает цикл $C$ в двух точках из $C[a,b]$ (случай $C[b,a]$ рассматривается аналогично), то в $G'$ имеется цикл, содержащий внутри себя больше граней, чем цикл $C$, и проходящий через $a$ и $b$, что невозможно. Итого, внешняя часть встречает цикл $C$ хотя бы в двух точках, никакие две из которых не лежат в $C[a,b]$ и $C[b,a]$. То есть ровно одна лежит в $C(a,b)$ и ровно одна — в $C(b,a)$. $\triangleleft$ Определение: Ввиду леммы 1 будем говорить, что любая внешняя часть является $(a,b)$ — разделяющей частью (англ. separating part), поскольку она встречает и $C(a,b)$, и $C(b,a)$. Аналогично можно ввести понятие $(a,b)$ — разделяющей внутренней части. Заметим, что внутренняя часть может встречать цикл $C$, вообще говоря, более чем в двух точках, но не менее чем в двух точках. Лемма (2): Существует хотя бы одна $(a,b)$ — разделяющая внутренняя часть. Доказательство: $\triangleright$ Пусть, от противного, таких частей нет. Тогда, выходя из $a$ внутри области, ограниченной $C$, и двигаясь вблизи от $C$ по направлению обхода $C$ и вблизи от встречающихся внутренних частей, можно уложить ребро $e = ab$ внутри цикла $C$, т.е. $G$ — планарный граф, что невозможно. $\triangleleft$ Лемма (3): Существует внешняя часть, встречающая $C(a,b)$ в точке $c$ и $C(b,a)$ — в точке $d$, для которой найдётся внутренняя часть, являющаяся одновременно $(a,b)$ — разделяющей и $(c,d)$ — разделяющей. Доказательство: $\triangleright$ Пусть, от противного, лемма 3 неверна. Упорядочим $(a,b)$ — разделяющие внутренние части в порядке их прикрепления к циклу $C$ при движении по циклу от $a$ до $b$ и обозначим их соответственно через $In_{1},In_{2},\dots$ Пусть $u_{1}$ и $u_{2}$ — первая и последняя вершины из $C(a,b)$, в которых $In_{1}$ встречает цикл $C$, а $v_{1}$ и $v_{2}$ — первая и последняя вершины из $C(b,a)$, в которых $In_{1}$ встречает цикл $C$ (возможно, вообще говоря, $u_{1} = u_{2}$ или $v_{1} = v_{2}$). Поскольку лемма 3 неверна, для любой внешней части обе её вершины, в которых она встречает $C$, лежат либо на $C[v_{2},u_{1}]$, либо на $C[u_{2},v_{1}]$. Тогда снаружи цикла $C$ можно провести жорданову кривую $P$, не пересекая рёбер графа $G'$, соединяющую $v_{2}$ с $u_{1}$. Поскольку на участках $C(u_{1},u_{2})$ и $C(v_{1},v_{2})$ нет точек прикрепления внешних частей, используя жорданову кривую $P$, внутреннюю часть $In_{1}$ можно перебросить ("вывернуть" наружу от цикла $C$) во внешнюю область цикла $C$, т.е. уложить её снаружи от цикла $C$ и сделать её внешней частью. Аналогично все остальные $(a,b)$ — разделяющие внутренние части можно перебросить во внешнюю область от цикла $C$. После этого точно так же, как в доказательстве леммы 2, ребро $e = ab$ можно уложить внутри цикла $C$, так как не останется $(a,b)$ — разделяющих внутренних частей. Следовательно, мы получим укладку графа $G$, что невозможно. $\triangleleft$ Разбор случаев взаимного положения вершин a, b, c, d, u1, u2, v1, v2 Пусть пара вершин $\ v_1$ и $\ v_2$ является $(a, b)$ — разделяющей. Тогда, в частности, $v_2 \ne a$ и $v_1 \ne b$. В этом случае граф $G$ содержит подграф, гомеоморфный $\ K_{3,3}$ (отметим, что в $In$ существует простая $(v_1, v_2)$ — цепь). Пусть пара вершин $v_1$ и $v_2$ не является $(a, b)$ — разделяющей. Тогда $v_1, v_2$ лежат на $C[a, b]$ или на $C[b, a]$. Без ограничения общности будет считать, что $v_1$ и $v_2$ лежат на $C[a, b]$. Пусть $v_1$ и $v_2$ лежат на $C(a, b)$, т.е. $v_1 \ne b$ и $v_2 \ne a$. Пусть $u_2$ лежит на $C(d, a)$. Тогда в графе $G$ имеется подграф, гомеоморфный $K_{3,3}$. Пусть $u_2 = d$. Тогда во внешней части $In$ имеется вершина $w$ и три простые цепи от $w$ соответственно до $d, v_1, v_2$, которые в качестве общей точки имеют только точку $w$. В этом случае в графе $G$ имеется подграф, гомеоморфный $K_{3,3}$. Пусть $u_2$ лежит на $C(b, d)$. Тогда в графе $G$ есть подграф, гомеоморфный $K_{3,3}$. Теперь рассмотрим случаи (2 и 3), когда хотя бы одна из вершин $v_1$ и $v_2$ не лежит на $С(a, b)$. Без ограничения общности будем считать, что это вершина $v_1$, т.е $v_1 = b$(поскольку $v_1$ лежит на $C[a, b]$). Пусть $v_2 \ne a$. Пусть $u_2$ лежит на $C(d, a)$. Тогда в графе $G$ есть пограф, гомеоморфный $K_{3,3}$. Пусть $u_2 = d$. Тогда в графе $G$ имеется подграф, гомеоморфный $K_{3,3}$. Пусть $u_2$ лежит на $C(b, d)$. Тогда в графе $G$ имеется подграф, гомеоморфный $K_{3,3}$. Пусть $v_2 = a$. Рассмотрим теперь пару вершин $u_1$ и $u_2$. Будем считать, что $u_1 = c$ и $u_2 = d$, поскольку все другие случаи расположения вершин $u_1$ и $u_2$ так же, как были рассмотрены все случаи расположения $v_1$ и $v_2$. Пусть $P_1$ и $P_2$ — соответственно кратчайшие простые $(a, b)$ — цепь и $(c, d)$-цепь по внутренней части $In$. Заметим, что $P_1$ и $P_2$ имеют общую точку. Пусть цепи $P_1$ и $P_2$ имеют более одной общей точки. Тогда в графе $G$ есть подграф, гомеоморфный $K_{3,3}$. Пусть цепи $P_1$ и $P_2$ имеют точно одну общую точку $w$. Тогда в графе $G$ есть подграф, гомеоморфный $K_5$. Таким образом, доказано, что в графе $G$ имеется подграф, гомеоморфный $K_{3,3}$ или $K_5$, что противоречит нашему первому предположению.

$\triangleleft$

См. также

• Двойственный граф планарного графа
• Теорема Фари

Источники информации

• Википедия — Планарный граф
• Wikipedia — Kuratowski's theorem
• "Вокруг критерия Куратовского планарности графов" (стр. 118)
• Асанов М., Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы