Изменения

Граф [[Укладка_графа_на_плоскости| планарен ]] тогда и только тогда, когда он не содержит подграфов, [[Укладка графа на плоскости #def_hmp| гомеоморфных ]] <tex> K_{5} </tex>, и не содержит подграфов, гомеоморфных или <tex> K_{3, 3} </tex> .

=== Необходимость ===Заметим, что из планарности графа следует планарность гомеоморфного графа и наоборот. В самом деле, пусть <tex> G_1 </tex> {{---}} плоский граф.Необходимость условия очевиднаЕсли добавить на нужных ребрах вершины степени <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> {{--- }} такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин. ==== G связен ====Если <tex> G </tex> не [[Отношение_связности,_компоненты_связности|связен]], то в силу минимальности <tex> G </tex> его компоненты связности планарны и, следовательно, сам граф <tex> G </tex> планарен.==== G {{- --}} обыкновенный граф ====В самом деле, пусть в графе <tex> G </tex> есть петля или кратное ребро <tex> e </tex>. Тогда в силу минимальности <tex> G </tex> граф <tex> G - e </tex> планарен. Добавляя ребро <tex> e </tex> к графу <tex> G - e </tex> получим, что граф <tex> G </tex> он планарен.==== G {{- --}} [[Отношение_вершинной_двусвязности|блок =]] ===Пусть, от противного, в графе есть [[Точка_сочленения,_эквивалентные_определения|точка сочленения ]] <tex> v </tex>. Через <tex> G_1 </tex> обозначим подграф графа <tex> G </tex>, порождённый вершинами одной из компонент связности графа <tex> G - v</tex> и вершинной <tex> v </tex>, а через <tex> G_2 </tex> подграф графа <tex> G </tex>, порождённый вершинами остальных компонент связности графа <tex> G - v </tex> и вершиной <tex> v </tex>. (рис В силу минимальности <tex> G </tex>, <tex> G_1 </tex> и <tex> G_2 </tex> {{---}} планарны. 1) [[Файл:p-kNew.nb.pic.1.png|thumb|right400px|рис. 1]] Возьмём укладку графа <tex> G_1 </tex> на плоскости такую, что вершина <tex> v </tex> лежит на границе верхней внешней грани. Ее можно получить, взяв любую укладку <tex> G_1 </tex> на плоскости, по ней построив укладку на шаре, используя обратную стереографическую проекцию<ref> [http://en.wikipedia.org/wiki/Stereographic_projection Wikipedia {{---}} Stereographic projection] </ref>, потом повернуть сферу так, чтоб <tex> v </tex> оказалась на внешней гранистереографической проекции повернутого шара.  Затем во внешней грани графа <tex> G_1 </tex> возьмём укладку графа <tex> G_2 </tex> такую, что вершина <tex> v </tex> будет представлена на плоскости в двух экземплярах. (рис. 2) [[Файл:p-knb.pic.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) [[Файл:p-knb.pic.3.png|thumb|right400px|рис. 3]] 

=== В G нет мостов === Граф <tex> G <br/tex> не равен <tex> K_2 <br/tex>и в нем нет точек сочленения, следовательно в <tex> G </tex> нет [[Мост,_эквивалентные_определения|мостов]]. === В G' существует цикл, содержащий вершины a и b ===Пусть <tex> e = ab </tex> {{--- }} произвольное ребро графа <tex> G </tex>, <tex> G' = G - e </tex>.

# Если <tex> |VB| >= \geqslant 3 </tex>, то существует цикл графа G', содержащий вершины <tex> a </tex> и <tex> b </tex>.

# Если вершины <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> e1 e_1 = vb </tex> - новое ребро (рис. 4)[[Файл:p-k.4.png|thumb|right|рис. 4]]Заметим, что в графе <tex> G''_1 </tex> рёбер меньше, чем в графе <tex> G </tex>. Действительно, вместо ребра <tex> e </tex> в <tex> G''_1 </tex> есть ребро <tex> e1 </tex> и часть рёбер из графа <tex> G </tex> осталась в графе <tex> G''_2 </tex>. Аналогично, в графе <tex> G''_2 </tex> рёбер меньше, чем в графе <tex> G </tex>. <br/>Покажем, далее, что в графе <tex> G''_1 </tex> и, аналогично, в графе <tex> G''_2 </tex> нет подграфов, гомеоморфных <tex> K_5 </tex> или <tex> K_{3,3} </tex>. Действительно, если в <tex> G''_1 </tex> имеется такой подграф, то в этом подграфе присутствует вновь присоединенное ребро, но это ребро <tex> e1 </tex> можно заменить на цепь <br/>a {-> b -> ... -> v, <br/> взяв некоторую простую (b, v)-цепь <tex> P_2 </tex> в графе <tex> G'_2 </tex>. Следовательно, мы получили подграф в <tex> G </tex>, гомеоморфный <tex> К_5 </tex> или <tex> К_{3,3} </tex>, что невозможно. <br/> Теперь в силу минимальности графа <tex> G </tex> графы <tex> G''_1 </tex> и <tex> G''_2 </tex> планарны. Возьмем укладку графа <tex> G''_1 </tex> на плоскости такую, что } новое ребро <tex> е1 = av </tex> лежит на границе внешней грани. Во внешней грани графа <tex> G''_1 </tex> возьмем укладку графа <tex> G''_2 </tex> такую, что ребро <tex> е2 = vb </tex> лежит па границе внешпей грани (рис. 5). [[Файл:p-k.5.png|thumb|right|рис. 5]]Отметим, что опять вершина <tex> v </tex> представлена на плоскости в двух экземплярах. Очевидно, добавление ребра <tex> е = ab </tex> не меняет планарности графа <tex> G''_1 U G''_2</tex>. Склеим оба вхождения вершины <tex> v </tex> точно так же, как это мы сделали в предыдущем пункте доказательства (рис. 6). [[Файл:p-k.6.png|thumb|right|рис. 6]]Сотрем затем ранее добавленные ребра <tex> е1 </tex> и <tex> е2 </tex>. В результате мы получим укладку графа <tex> G </tex> на плоскости, что невозможно. Утверждение доказано.

Заметим, что в графе <tex> G''_1 </tex> рёбер меньше, чем в графе <tex> G </tex>. Действительно, вместо ребра <tex> e </tex> в <tex> G''_1 </tex> есть ребро <tex> e_1 </tex> и часть рёбер из графа <tex> G </tex> осталась в графе <tex> G''_2 </tex>. Аналогично, в графе <tex> G''_2 </tex> рёбер меньше, чем в графе <tex> G </tex>. <br/>Теперь в силу минимальности графа <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> лежит па границе внешней грани. [[Файл:nb.pic.5.png|400px|рис. 5]] Отметим, что опять вершина <tex> v </tex> представлена на плоскости в двух экземплярах. Очевидно, добавление ребра <tex> e = ab </tex> не меняет планарности графа <tex> G''_1 U G''_2</tex>. Склеим оба вхождения вершины <tex> v </tex> точно так же, как это мы сделали в предыдущем пункте доказательства. [[Файл:nb.pic.6.png|400px|рис. 6]] Сотрем затем ранее добавленные ребра <tex> e_1 </tex> и <tex> e_2 </tex>. В результате мы получим укладку графа <tex> G </tex> на плоскости, что невозможно. Утверждение доказано. ===Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части===Среди всех укладок графа <mathtex>G'</mathtex> на плоскости и среди всех циклов <mathtex>C</mathtex>, содержащих <mathtex>a</mathtex> и <mathtex>b</mathtex>, зафиксируем такую укладку и такой цикл, что внутри области, ограниченной циклом <mathtex>C</mathtex>, лежит максимальное возможное число граней графа <mathtex>G'</mathtex>. Зафиксируем один из обходов по циклу <mathtex>C</mathtex> (на рисунках будем рассматривать обход по часовой стрелке по циклу <mathtex>C</mathtex>). Для вершин <mathtex>u</mathtex> и <mathtex>v</mathtex> цикла <mathtex>C</mathtex> через <mathtex>C[u,v]</mathtex> будем обозначать простую <mathtex>(u,v)</mathtex>{{---}} цепь, идущую по циклу <mathtex>C</mathtex> от <mathtex>u</mathtex> до <mathtex>v</mathtex> в направлении обхода цикла. Конечно, <mathtex>C[u,v] ≠ \ne C[v,u]</mathtex>. Положим <mathtex>C(u,v) = C[u,v]\setminus</tex> {<tex>u,v}</mathtex>}, т.е. <mathtex>C(u,v)</mathtex> получено из <mathtex>C[u,v]</mathtex> отбрасыванием вершин <mathtex>u</mathtex> и <mathtex>v</mathtex>.

<b>Внешним графом </b> (англ. ''Outside graph'') (относительно цикла <mathtex>C</mathtex>) будем называть подграф графа <mathtex>G'</mathtex>, порождённый всеми вершинами графа <mathtex>G'</mathtex>, лежащими снаружи от цикла <mathtex>C</mathtex>.

<b>Внешними компонентами </b> (англ. ''Outside components'') будем называть компоненты связности внешнего графа.

В силу связности графа <mathtex>G'</mathtex> для любой внешней компоненты должны существовать рёбра в <mathtex>G'</mathtex>, соединяющие её с вершинами цикла <mathtex>C</mathtex>.

<b>Внешними частями </b> (англ. ''Outside parts'') будем называть: a) внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <mathtex>C</mathtex>, и инцидентными им вершинами; б) , либо рёбра графа <mathtex>G'</mathtex>, лежащие снаружи от цикла <mathtex>C</mathtex> и соединяющие две вершины из <mathtex>C</mathtex>, вместе с инцидентными такому ребру вершинами.

[[Файл:nb.pic.7.png|440px|рис. 7]]{{ОпределиниеОпределение

<b>Внутренним графом </b> (англ. ''Inside graph'') (относительно цикла <mathtex>C</mathtex>) будем называть подграф графа <mathtex>G'</mathtex>, порождённый всеми вершинами графа <mathtex>G'</mathtex>, лежащими внутри цикла <mathtex>C</mathtex>.

<b>Внутренними компонентами </b> (англ. ''Inside components'') будем называть компоненты связности внутреннего графа.

В силу связности графа <mathtex>G'</mathtex> для любой внутренней компоненты должны существовать рёбра в <mathtex>G'</mathtex>, соединяющие её с вершинами цикла <mathtex>C</mathtex>.

<b>Внутренними частями </b> (англ. ''Inside parts'') будем называть: a) внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <mathtex>C</mathtex>, и инцидентными им вершинами; б) , либо рёбра графа <mathtex>G'</mathtex>, лежащие внутри цикла <mathtex>C</mathtex> и соединяющие две вершины из <mathtex>C</mathtex>, вместе с инцидентными такому ребру вершинами.

Будем говорить, что внешняя (внутренняя) часть ''встречает цикл'' <mathtex>C</mathtex> в своих точках прикрепления к циклу <mathtex>C</mathtex>.{{Утверждение 5Лемма|about=1

Любая внешняя часть встречает цикл <mathtex>C</mathtex> точно в двух точках, одна из которых лежит в <mathtex>C(a,b)</mathtex>, а другая {{- --}} в <mathtex>C(b,a)</mathtex>.

Если внешняя часть встречает цикл <mathtex>C</mathtex> точно в одной точке <mathtex>v</mathtex>, то <mathtex>v</mathtex> является точкой сочленения графа <mathtex>G</mathtex>, что невозможно. [[Файл:nb.pic.8.png|420px|рис. 8]] Таким образом, внешняя часть встречает цикл <mathtex>C</mathtex> не менее чем в двух точках. Если внешняя часть встречает цикл <mathtex>C</mathtex> в двух точках из <mathtex>C[a,b]</mathtex> (случай <mathtex>C[b,a]</mathtex> рассматривается аналогично), то в <mathtex>G'</mathtex> имеется цикл, содержащий внутри себя больше граней, чем цикл <mathtex>C</mathtex>, и проходящий через <mathtex>a</mathtex> и <mathtex>b</mathtex>, что невозможно. [[Файл:nb.pic.9.png|420px|рис. 9]] Итого, внешняя часть встречает цикл <mathtex>C</mathtex> хотя бы в двух точках, никакие две из которых не лежат в <mathtex>C[a,b]</mathtex> и <mathtex>C[b,a]</mathtex>. То есть ровно одна лежит в <mathtex>C[(a,b])</mathtex> и ровно одна {{--- }} в <mathtex>C[(b,a])</mathtex>.

Ввиду утверждения 5 леммы 1 будем говорить, что любая внешняя часть является <mathb><tex>(a,b)</mathtex>{{---}} разделяющей частью</b> (англ. ''separating part''), поскольку она встречает и <mathtex>C(a,b)</mathtex>, и <mathtex>C(b,a)</mathtex>.

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

Существует хотя бы одна <mathtex>(a,b)</mathtex>{{---}} разделяющая внутренняя часть.

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

{{Утверждение 7Лемма|about=3

Существует внешняя часть, встречающая <mathtex>C(a,b)</mathtex> в точке <mathtex>c</mathtex> и <mathtex>C(b,a)</mathtex> {{--- }} в точке <mathtex>d</mathtex>, для которой найдётся внутренняя часть, являющаяся одновременно <mathtex>(a,b)</mathtex>{{---}} разделяющей и <mathtex>(c,d)</math>-разделяющей.|proof =Пусть, от противного, утверждение 7 неверно. Упорядочим <math>(a,b)</math>-разделяющие внутренние части в порядке их прикрепления к циклу <math>C</math> при движении по циклу от <math>a</math> до <math>b</math> и обозначим их соответственно через <mathtex>In_{1},In_{2},...</math>. Пусть <math>u_{1}</math> и <math>u_{2}</math> - первая и последняя вершины из <math>C(a,b)</math>, в которых <math>In_{1}</math> встречает цикл <math>C</math>, а <math>v_{1}</math> и <math>v_{2}</math> - первая и последняя вершины из <math>C(b,a)</math>, в которых <math>In_{1}</math> встречает цикл <math>C</math> (возможно, вообще говоря, <math>u_{1-} = u_{2}</math> или <math>v_{1} = v_{2}</math>)разделяющей. Поскольку 7 неверно, для любой внешней части обе её вершины, в которых она встречает <mathbr>C</math>, лежат либо на <math>C[v_{2},u_{1}]</math>, либо на <math>C[u_{2},v_{1}]</math>. Тогда снаружи цикла <math>C</math> можно провести жорданову кривую <math>P</math>, не пересекая рёбер графа <math>G'</math>, соединяющую <math>v_{2}</math> с <math>u_{1}</math>.Поскольку на участках <math>C(u_{1},u_{2})</math> и <math>C(v_{1},v_{2})</math> нет точек прикрепления внешних частей, используя жорданову кривую <math>P</math>, внутреннюю часть <math>In_{1}</math> можно перебросить ("вывернуть" наружу от цикла <math>C</math>) во внешнюю область цикла <math>C</math>, т.е. уложить её снаружи от цикла <math>C</math> и сделать её внешней частью.Аналогично все остальные <math>(a,b)</math>-разделяющие внутренние части можно перебросить во внешнюю область от цикла <math>C</math>. После этого точно так же, как в доказательстве утверждения 6, ребро <math>e = ab</math> можно уложить внутри цикла <math>C</math>, так как не останется <math>(a,b)</math>-разделяющих внутренних частей. Следовательно, мы получим укладку графа <math>G</math>, что невозможно.}}

==== Разбор случаев взаимного положения ''a, b, c, d, u1, u2, v1, v2'' ====Рассмотрим 2 случая.[[Файл:Case_1nb.pic.11.png|thumb|right240px|рис. 111]]----

|proof =Пусть, от противного, лемма 3 неверна. Упорядочим <tex>(a,b)</tex> {{---}} разделяющие внутренние части в порядке их прикрепления к циклу <tex>C</tex> при движении по циклу от <tex>a</tex> до <tex>b</tex> и обозначим их соответственно через <tex>In_{1. },In_{2},\dots</tex> Пусть пара вершин <tex>\ v_1 u_{1}</tex> и <tex>\ v_2 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)<br/tex>Тогда, в частностикоторых <tex>In_{1}</tex> встречает цикл <tex>C</tex> (возможно, вообще говоря, <tex>v_2 \ne au_{1} = u_{2}</tex> и или <tex> v_1 \ne bv_{1} = v_{2}</tex>). В этом случае граф G содержит подграфПоскольку лемма 3 неверна, для любой внешней части обе её вершины, в которых она встречает <tex>C</tex>, гомеоморфный лежат либо на <tex>\ K_C[v_{32},3u_{1} ]</tex> (отметим, что в либо на <tex>C[u_{2},v_{1}]</tex>. Тогда снаружи цикла <tex>C</tex> можно провести жорданову кривую <tex> In P</tex> существует простая , не пересекая рёбер графа <tex>(v_1G'</tex>, v_2)соединяющую <tex>v_{2}</tex>-цепь)(рис. с <tex>u_{1)}</tex>.

----2[[Файл:nb. Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> не является <tex>(a, b)</tex>-разделяющейpic. <br>Тогда <tex>v_1, v_2</tex> лежат на <tex>C[a, b12.png|310px|рис. 12]</tex> или на <tex>C[b, a]</tex>. Без ограничения общности будет считать, что <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C[a, b]</tex>.<br>

Поскольку на участках <tex>C(u_{1},u_{2.})</tex> и <tex>C(v_{1. Пусть },v_{2})</tex> нет точек прикрепления внешних частей, используя жорданову кривую <tex>v_1P</tex> и , внутреннюю часть <tex>v_2In_{1}</tex> лежат на можно перебросить ("вывернуть" наружу от цикла <tex>C(a, b</tex>)во внешнюю область цикла <tex>C</tex>, т.е. уложить её снаружи от цикла <tex>v_1 \ne bC</tex> и сделать её внешней частью.Аналогично все остальные <tex>v_2 \ne (a,b)</tex> {{---}} разделяющие внутренние части можно перебросить во внешнюю область от цикла <tex>C</tex>(рис. После этого точно так же, как в доказательстве леммы 2, ребро <tex>e = ab</tex> можно уложить внутри цикла <tex>C</tex>, так как не останется <tex>(a,b)</tex> {{---}} разделяющих внутренних частей. Следовательно, мы получим укладку графа <tex>G<br/tex>, что невозможно.}}

2.1.2. == Разбор случаев взаимного положения вершин ''a, b, c, d, u1, u2, v1, v2'' ==* Пусть пара вершин <tex>u_2 = d\ v_1 </tex>.<br>Тогда во внешней части и <tex>In\ v_2 </tex> имеется вершина <texb>wявляется </texb> и три простые цепи от <tex>w(a, b)</tex> соответственно до {{---}} разделяющей. <texbr>d*: Тогда, v_1в частности, <tex>v_2\ne a</tex>, которые в качестве общей точки имеют только точку и <tex>wv_1 \ne b</tex>. *: В этом случае в графе граф <tex>G имеется </tex> содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex>(рис. 4отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2).<br/tex>{{---}} цепь).

2;: [[Файл:Case_1.1.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>Тогда в графе G есть подграф, гомеоморфный <tex>K{3,3}</tex>(png|270px|рис. 5)7.<br>1]]

* Пусть пара вершин <ptex>v_1</tex> и <tex>v_2</tex> <b> не является </b> <tex>(a, b)</tex> {{---}} разделяющей. <br>*: Тогда <tex>v_1, v_2</tex> лежат на <tex>C[a, b]</tex> или на <tex>C[b, a]</tex>. *: Без ограничения общности будет считать, что <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C[a, b]</tex>.<br>*: <br>*# <b>Пусть <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C(a, b)</tex>, т.е. <tex>v_1 \ne b</tex> и <tex>v_2 \ne a</tex>. <br></b>*## Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>*##: Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>.*##: [[Файл:Сase_2.1.1.png|150px200px|рис. 7.3]]*## Пусть <tex>u_2 = d</tex>.<br>*##:Тогда во внешней части <tex>In</tex> имеется вершина <tex>w</tex> и три простые цепи от <tex>w</tex> соответственно до <tex>d, v_1, v_2</tex>, которые в качестве общей точки имеют только точку <tex>w</tex>. *##:В этом случае в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>*##:[[Файл:Сase_2.1. 2.png|200px|рис. 7.4]]*## Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>*##:Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>*##:[[Файл:Сase_2.1.3.png|200px|рис. 7.5]]*#:<br>*#:Теперь рассмотрим случаи (2 и 3), когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>. *#:Без ограничения общности будем считать, что это вершина <tex>v_1</tex>, т.е <tex>v_1 = b</tex>(поскольку <tex>v_1</tex> лежит на <tex>C[a, b]</tex>).<br>*#:<br>*# <b> Пусть <tex>v_2 \ne a</tex>.<br> </b>*##: Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>*##: Тогда в графе <tex>G</tex> есть пограф, гомеоморфный <tex>K_{3,3}</tex>.<br>*##:[[Файл:Сase_2.2.1.png|150px200px|рис. 7.6]]*## Пусть <tex>u_2 = d</tex>.<br>*##:Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>*##:[[Файл:Сase_2.2.2.png|220px|рис. 7.7]]*## Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>*##:Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>. <br>*##:[[Файл:Сase_2.12.3.png|200px|рис. 7.8]]*#:<br>*#:<br>*# <b> Пусть <tex>v_2 = a</tex>.<br> </b>*#:[[Файл:Сase_2.23(a).png|150px200px|рис. 47.9]]*#:Рассмотрим теперь пару вершин <tex>u_1</tex> и <tex>u_2</tex>. *#:Будем считать, что <tex>u_1 = c</tex> и <tex>u_2 = d</tex>, поскольку все другие случаи расположения вершин <tex>u_1</tex> и <tex>u_2</tex> так же, как были рассмотрены все случаи расположения <tex>v_1</tex> и <tex>v_2</tex>. *#:Пусть <tex>P_1</tex> и <tex>P_2</tex> {{---}} соответственно кратчайшие простые <tex>(a, b)</tex> {{---}} цепь и <tex>(c, d)</tex>-цепь по внутренней части <tex>In</tex>.*#:[[Файл:Сase_2.13(b).png|200px|рис. 7.10]]*#:Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br>*#: <br>*## Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>*##: Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex>.<br>*##: [[Файл:Сase_2.3.1.png|150px200px|рис. 57.11]]*## Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>*##: Тогда в графе <tex>G</ptex>есть подграф, гомеоморфный <tex>K_5</tex>.<br>*##: [[Файл:Сase_2.3.2.png|200px|рис. 7.12]]

Теперь рассмотрим случаи, когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>== См. Без ограничения общности будем считать, что это вершина <tex>v_1</tex>, т.е <tex>v_1 также == b</tex>(поскольку <tex>v_1</tex> лежит на <tex>C* [a, b[Двойственный граф планарного графа]]* [[Теорема Фари]]</tex>).<br>

2.2. Пусть <tex>v_2 \ne a</tex>.<br> 2.2.1. Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>Тогда в графе G есть пограф, гомеоморфный <tex>K_{3,3}</tex>(рис. 6).<br> 2.2.2. Пусть <tex>u_2 = d</tex>.<br>Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 7).<br> 2.2.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 8). <br><p>[[Файл:Сase_2.2.1.png|150px|рис. 6]][[Файл:Сase_2.2.2.png|150px|рис. 7]][[Файл:Сase_2.2.3.png|150px|рис. 8]]</p> ---- 2.3. Пусть <tex>v_2 = a</tex>(рис. 9).<br>Рассмотрим теперь пару вершин <tex>u_1</tex> и <tex>u_2</tex>. Будем считать, что <tex>u_1 Примечания = c</tex> и <tex>u_2 = d</tex>, поскольку все другие случаи расположения вершин <tex>u_1</tex> и <tex>u_2</tex> так же, как были рассмотрены все случаи расположения <tex>v_1</tex> и <tex>v_2</tex>. Пусть <tex>P_1</tex> и <tex>P_2</tex> -- соответственно кратчайшие простые <tex>(a, b)</tex>-цепь и <tex>(c, d)</tex>-цепь по внутренней части <tex>In</tex>(рис. 10).Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br> 2.3.1. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>Тогда в графе G есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 11).<br> 2.3.2. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>Тогда в графе G есть подграф, гомеоморфный <tex>K_5</tex>(рис. 12).<br> <p>[[Файл:Сase_2.3(a).png|150px|рис. 9]][[Файл:Сase_2.3(b).png|150px|рис. 10]][[Файл:Сase_2.3.1.png|150px|рис. 11]][[Файл:Сase_2.3.2.png|150px|рис. 12]]</p> Таким образом, доказано, что в графе G имеется подграф, гомеоморфный <tex>K_{3,3}<references /tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br>}}

==ЛитератураИсточники информации==* [https://ru.wikipedia.org/wiki/Планарный_граф Википедия {{---}} Планарный граф]* [http://en.wikipedia.org/wiki/Kuratowski's_theorem Wikipedia {{---}} Kuratowski's theorem]* [http://acm.math.spbu.ru/~sk1/download/books/TheoremKuratowski.pdf "Вокруг критерия Куратовского планарности графов" (стр. 118)] * Асанов М,., Баранский В., Расин В. {{--- }} Дискретная математика {{--- }} Графы, матроиды, алгоритмы