Изменения

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

Если добавить на нужных ребрах вершины степени <tex> 2 </tex> и удалить некотрые вершины степени <tex> 2 </tex> в <tex> G_1 </tex>, получим укладку гомеоморфного графа <tex> G_2 </tex>. Таким образом, доказательство достаточности необходимости следует из [[Непланарность_K5_и_K3,3| непланарности <tex>K_5</tex> и <tex>K_{3, 3}</tex>]].

Докажем неоходимостьдостаточность. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Пусть <tex> G </tex> {{---}} такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.

<tex> G_2 </tex> подграф графа <tex> G </tex>, порождённый вершинами остальных компонент связности графа <tex> G - v </tex> и вершиной <tex> v </tex>. (рис. 1)

 [[Файл:New.p-knb.pic.1.png|thumb|right400px|рис. 1]] 

Затем во внешней грани графа <tex> G_1 </tex> возьмём укладку графа <tex> G_2 </tex> такую, что вершина <tex> v </tex> будет представлена на плоскости в двух экземплярах. (рис. 2) [[Файл:Newnb.p-kpic.2.png|thumb|right400px|рис. 2]] Соединим два экземпляра вершины <tex> v </tex> пучком жордановых линий, не допуская лишних пересечений с укладками графов <tex> G_1 </tex> и <tex> G_2 </tex>, состоящим из такого количества линий, какова степень вершины <tex> v </tex> в графе <tex> G_2 </tex>. Далее отбросим вхождение вершины <tex> v </tex> в граф <tex> G_2 </tex>, заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер (рис. 3) [[Файл:Newnb.p-kpic.3.png|thumb|right400px|рис. 3]] 

#Если вершины <tex> a </tex> и <tex> b </tex> лежат в разных блоках графа <tex> G' </tex>, что существует точка сочленения <tex> v </tex>, принадлежащая любой простой <tex> (a, b) </tex> {{---}} цепи графа <tex> G' </tex>. Через <tex> G'_1 </tex> обозначим подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами компоненты связности графа <tex> G' - v </tex>, содержащей <tex> a </tex>, а через <tex> G'_2 </tex> {{---}} подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами остальных компонент связности графа <tEx> G' - v </tex> (в этом множестве лежит вершина <tex> b </tex>). Пусть <tex> G''_1 = G'_1 + e_1 </tex>, где <tex> e_1 = vb </tex> {{---}} новое ребро (рис. 4) [[Файл:Newnb.p-kpic.4.png|thumb|right400px|рис. 4]] 

Теперь в силу минимальности графа <tex> G </tex> графы <tex> G''_1 </tex> и <tex> G''_2 </tex> планарны. Возьмем укладку графа <tex> G''_1 </tex> на плоскости такую, что ребро <tex> e_1 = av </tex> лежит на границе внешней грани(ее существование доказывается аналогично существованию такой укладки для вершины графа). Во внешней грани графа <tex> G''_1 </tex> возьмем укладку графа <tex> G''_2 </tex> такую, что ребро <tex> e_2 = vb </tex> лежит па границе внешней грани (рис. 5).  [[Файл:Newnb.p-kpic.5.png|thumb|right400px|рис. 5]] Отметим, что опять вершина <tex> v </tex> представлена на плоскости в двух экземплярах. Очевидно, добавление ребра <tex> e = ab </tex> не меняет планарности графа <tex> G''_1 U G''_2</tex>. Склеим оба вхождения вершины <tex> v </tex> точно так же, как это мы сделали в предыдущем пункте доказательства (рис. 6).  [[Файл:Newnb.p-kpic.6.png|thumb|right400px|рис. 6]] 

[[Файл:pict-1nb.jpg|center|200px|рисpic. 7]][[Файл:pict-2.jpgpng|center|125px440px|рис. 87]]

 [[Файл:pict-3nb.jpgpic.8.png|center420px|рис. 98]] 

 [[Файл:pict-4nb.jpgpic.9.png|center420px|рис. 109]] 

Аналогично можно ввести понятие <tex>(a,b)</tex> {{---}} разделяющей внутренней части. Заметим, что внутрення внутренняя часть может встречать цикл <tex>C</tex>, вообще говоря, более чем в двух точках, но не менее чем в двух точках.

Пусть, от противного, таких частей нет. Тогда, выходя из <tex>a</tex> внутри области, ограниченной <tex>C</tex>, и двигаясь вблизи от <tex>C</tex> по направлению обхода <tex>C</tex> и вблизи от встречающихся внутренних частей, можно уложить ребро <tex>e = ab</tex> внутри цикла <tex>C</tex>, т.е. <tex>G</tex> {{---}} планарный граф, что невозможно. [[Файл:pict-5nb.jpg|centerpic.10.png|180px280px|рис. 1110]] 

Существует внешняя часть, встречающая <tex>C(a,b)</tex> в точке <tex>c</tex> и <tex>C(b,a)</tex> {{---}} в точке <tex>d</tex>, для которой найдётся внутренняя часть, являющаяся одновременно <tex>(a,b)</tex> {{---}} разделяющей и <tex>(c,d)</tex> {{---}} разделяющей.<br> [[Файл:pict-6nb.jpgpic.11.png|center|160px240px|рис. 1211]] 

Пусть, от противного, лемма 3 неверна. Упорядочим <tex>(a,b)</tex> {{---}} разделяющие внутренние части в порядке их прикрепления к циклу <tex>C</tex> при движении по циклу от <tex>a</tex> до <tex>b</tex> и обозначим их соответственно через <tex>In_{1},In_{2},...\dots</tex> Пусть <tex>u_{1}</tex> и <tex>u_{2}</tex> {{---}} первая и последняя вершины из <tex>C(a,b)</tex>, в которых <tex>In_{1}</tex> встречает цикл <tex>C</tex>, а <tex>v_{1}</tex> и <tex>v_{2}</tex> {{---}} первая и последняя вершины из <tex>C(b,a)</tex>, в которых <tex>In_{1}</tex> встречает цикл <tex>C</tex> (возможно, вообще говоря, <tex>u_{1} = u_{2}</tex> или <tex>v_{1} = v_{2}</tex>). Поскольку лемма 3 неверна, для любой внешней части обе её вершины, в которых она встречает <tex>C</tex>, лежат либо на <tex>C[v_{2},u_{1}]</tex>, либо на <tex>C[u_{2},v_{1}]</tex>. Тогда снаружи цикла <tex>C</tex> можно провести жорданову кривую <tex>P</tex>, не пересекая рёбер графа <tex>G'</tex>, соединяющую <tex>v_{2}</tex> с <tex>u_{1}</tex>. [[Файл:pict-7nb.pic.12.jpg|centerpng|200px310px|рис. 1312]] 

* [http://en.wikipedia.org/wiki/Kuratowski's_theorem Wikipedia {{---}} Kuratowski's_theorems theorem]