Изменения

==== Разбор случаев взаимного положения Теорему доказал в 1927 году известный советский математик Лев Семенович Понтрягин, но не опубликовал.Независимо от Понтрягина в 1930 году доказательста нашел и впервые напечатал польский математик Казимир Куратовский.Первые доказательства теоремы Понтрягина-Куратовского были очень сложными. Сравнительно простое доказательство нашел в 1997 г. петербургский школьник Юрий Макарычев. <texbr>a, b, c, d, u1, u2, v1, v2</texbr> ====Рассмотрим 2 случая.

1. Пусть пара вершин <tex>\ v_1 </tex> {{Теорема|statement =Граф [[Укладка_графа_на_плоскости| планарен]] тогда и <tex>\ v_2 </tex> является <tex>(aтолько тогда, b)</tex>-разделяющей. <br>Тогда, в частностикогда он не содержит подграфов, [[Укладка графа на плоскости #def_hmp| гомеоморфных]] <tex>v_2 \ne aK_{5} </tex> и или <tex> v_1 \ne b</tex>. В этом случае граф G содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим.|proof =Заметим, что в из планарности графа следует планарность гомеоморфного графа и наоборот. В самом деле, пусть <tex> In </tex> существует простая <tex>(v_1, v_2)G_1 </tex>-цепь)(рис. 1).[[Файл:Case_1.png|thumb|right|рис. 1]]-{{---}} плоский граф.2. Пусть пара вершин Если добавить на нужных ребрах вершины степени <tex>v_12 </tex> и удалить некотрые вершины степени <tex>v_22 </tex> не является в <tex>(a, b)G_1 </tex>-разделяющей. <br>Тогда , получим укладку гомеоморфного графа <tex>v_1, v_2G_2 </tex> лежат на <tex>C. Таким образом, доказательство необходимости следует из [a, b]</tex> или на <tex>C[bНепланарность_K5_и_K3, a]</tex>. Без ограничения общности будет считать, что 3| непланарности <tex>v_1K_5</tex> и <tex>v_2K_{3, 3}</tex> лежат на <tex>C[a, b]</tex>].<br><br>

2Докажем достаточность.1От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Пусть <tex>v_1G </tex> и {{---}} такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин. === G связен ===Если <tex>v_2G </tex> лежат на не [[Отношение_связности,_компоненты_связности|связен]], то в силу минимальности <tex> G </tex>C(aего компоненты связности планарны и, следовательно, b)сам граф <tex> G </tex>планарен.=== G {{---}} обыкновенный граф ===В самом деле, тпусть в графе <tex> G </tex> есть петля или кратное ребро <tex> e </tex>.еТогда в силу минимальности <tex> G </tex> граф <tex> G - e </tex> планарен. Добавляя ребро <tex>v_1 \ne be </tex> и к графу <tex>v_2 \ne aG - e </tex>(рис. 2). получим, что граф <brtex>G <br/tex>планарен.=== G {{---}} [[Файл:Case_2.1.pngОтношение_вершинной_двусвязности|thumbблок]] ===Пусть, от противного, в графе есть [[Точка_сочленения,_эквивалентные_определения|right|рис. 2точка сочленения]]<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>.

2.1.1 Пусть В силу минимальности <tex>u_2G </tex> лежит на , <tex>C(d, a)G_1 </tex>.и <brtex>Тогда в графе G имеется подграф, гомеоморфный G_2 </tex>K_{3,3{---}}</tex>(рис. 3).<br><br>[[Файл:Сase_2.1.1.png|thumb|right|риспланарны. 3]]

2.1.2. Пусть <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>. В этом случае в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 4).<br><br>[[Файл:Сase_2New.nb.pic.1.2.png|thumb|right400px|рис. 41]]

2.1.3. Пусть Возьмём укладку графа <tex>u_2G_1 </tex> лежит на плоскости такую, что вершина <tex>C(b, d)v </tex>лежит на границе внешней грани.Ее можно получить, взяв любую укладку <tex> G_1 <br/tex>Тогда в графе G есть подграфна плоскости, по ней построив укладку на шаре, гомеоморфный используя обратную стереографическую проекцию<texref>K[http://en.wikipedia.org/wiki/Stereographic_projection Wikipedia {{3,3---}}Stereographic projection] </texref>(рис. 5)., потом повернуть сферу так, чтоб <brtex>v <br/tex>[[Файл:Сase_2оказалась на внешней грани стереографической проекции повернутого шара.1.3.png|thumb|right|рис. 5]]

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

2[[Файл:nb.pic.2. Пусть <tex>v_2 \ne a</tex>png|400px|рис.<br><br>2]]

2.2.1. Пусть Соединим два экземпляра вершины <tex> v </tex> пучком жордановых линий, не допуская лишних пересечений с укладками графов <tex>u_2G_1 </tex> лежит на и <tex> G_2 </tex>C(d, a)состоящим из такого количества линий, какова степень вершины </tex>.v <br/tex>Тогда в графе G есть пограф, гомеоморфный <tex>K_{3,3}G_2 </tex>(рис. 6).Далее отбросим вхождение вершины <tex> v </tex> в граф <brtex>G_2 <br/tex>[[Файл:Сase_2.2.1.png|thumb|right|рис, заменяя инцидентные ей рёбра на жордановы линии, полученные из линий указанного пучка и рёбер. 6]]

2.2.2. Пусть <tex>u_2 = d</tex>.<br>Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 7).<br><br>[[Файл:Сase_2nb.2pic.13.png|thumb|right400px|рис. 73]]

2Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно.2.3. Пусть === В G нет мостов === Граф <tex>u_2G </tex> лежит на не равен <tex>C(bK_2 </tex> и в нем нет точек сочленения, d)следовательно в <tex> G </tex>нет [[Мост,_эквивалентные_определения|мостов]].<br>Тогда в графе === В G имеется подграф' существует цикл, гомеоморфный содержащий вершины a и b ===Пусть <tex>K_e = ab </tex> {3{---}} произвольное ребро графа <tex> G </tex>,3}<tex> G' = G - e </tex>(рис. 8)# граф <tex> G' </tex> планарен в силу минимальности графа <tex> G </tex>. # граф <brtex> G' </tex>связен в силу отсутствия в графе <brtex>[[Файл:Сase_2G </tex> мостов.2.2.png|thumb|right|рис. 8]]

2.3. Пусть <tex>v_2 = a</tex>(рис. 9)и <tex> b </tex> лежат в одном блоке <tex> B </tex> графа <tex> G' </tex>.# Если <brtex>[[Файл:Сase_2.3(a).png|thumbVB|right|рис. 9]]Рассмотрим теперь пару вершин \geqslant 3</tex>, то существует цикл графа G', содержащий вершины <tex>u_1a </tex> и <tex>u_2b </tex>. Будем считать# Если <tex> |VB| = 2 </tex>, что то в <tex>u_1 = cB </tex> и имеется ребро <tex>u_2 e' = dab </tex>, поскольку все другие случаи расположения вершин но тогда в <tex> G </tex> имеются кратные рёбра <tex>u_1e </tex> и <tex>u_2e' </tex> так же, как были рассмотрены все случаи расположения что невозможно.#Если вершины <tex>v_1a </tex> и <tex>v_2b </tex>. Пусть лежат в разных блоках графа <tex>P_1G' </tex> и , что существует точка сочленения <tex>P_2v </tex> -- соответственно кратчайшие простые , принадлежащая любой простой <tex>(a, b)</tex>{{-цепь --}} цепи графа <tex> G' </tex>. Через <tex> G'_1 </tex> обозначим подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами компоненты связности графа <tex> G' - v </tex>, содержащей <tex>(ca </tex>, d)а через <tex> G'_2 </tex>{{---цепь по внутренней части }} подграф графа <tex>InG' </tex>(рис. 10).[[Файл:Сase_2.3(b).png|thumb|right|рис. 10]]Заметим, что порождённый вершиной <tex>P_1v </tex> и вершинами остальных компонент связности графа <tEx> G' - v </tex> (в этом множестве лежит вершина <tex>P_2b </tex> имеют общую точку).Пусть <brtex>G''_1 = G'_1 + e_1 <br/tex>, где <tex> e_1 = vb </tex> {{---}} новое ребро.

2.3.1. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>Тогда в графе G есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 11).<br><br>[[Файл:Сase_2nb.3pic.14.png|thumb|right400px|рис. 114]]

2Заметим, что в графе <tex> G''_1 </tex> рёбер меньше, чем в графе <tex> G </tex>.3.2. Пусть цепи Действительно, вместо ребра <tex> e </tex> в <tex> G''_1 </tex> есть ребро <tex>P_1e_1 </tex> и часть рёбер из графа <tex>P_2G </tex> имеют точно одну общую точку осталась в графе <tex> G''_2 </tex>. Аналогично, в графе <tex> G''_2 </tex> рёбер меньше, чем в графе <tex>wG </tex>.<br/>Тогда Теперь в графе силу минимальности графа <tex> G </tex> графы <tex> G''_1 </tex> и <tex> G''_2 </tex> планарны. Возьмем укладку графа <tex> G есть подграф''_1 </tex> на плоскости такую, гомеоморфный что ребро <tex>K_5e_1 = av </tex>лежит на границе внешней грани(рис. 12ее существование доказывается аналогично существованию такой укладки для вершины графа).Во внешней грани графа <brtex> G''_1 </tex> возьмем укладку графа <tex> G''_2 </tex> такую, что ребро <tex>e_2 = vb <br/tex>[[Файл:Сase_2.3.2.png|thumb|right|рислежит па границе внешней грани. 12]]

[[Файл: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> на плоскости, что невозможно. Утверждение доказано. ===Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части===Среди всех укладок графа <tex>G'</tex> на плоскости и среди всех циклов <tex>C</tex>, содержащих <tex>a</tex> и <tex>b</tex>, зафиксируем такую укладку и такой цикл, что внутри области, ограниченной циклом <tex>C</tex>, лежит максимальное возможное число граней графа <tex>G'</tex>. Зафиксируем один из обходов по циклу <tex>C</tex> (на рисунках будем рассматривать обход по часовой стрелке по циклу <tex>C</tex>). Для вершин <tex>u</tex> и <tex>v</tex> цикла <tex>C</tex> через <tex>C[u,v]</tex> будем обозначать простую <tex>(u,v)</tex> {{---}} цепь, идущую по циклу <tex>C</tex> от <tex>u</tex> до <tex>v</tex> в направлении обхода цикла. Конечно, <tex>C[u,v] \ne C[v,u]</tex>. Положим <tex>C(u,v) = C[u,v] \setminus</tex> {<tex>u,v</tex>}, т.е. <tex>C(u,v)</tex> получено из <tex>C[u,v]</tex> отбрасыванием вершин <tex>u</tex> и <tex>v</tex>.{{Определение|definition =<b>Внешним графом </b> (англ. ''Outside graph'') (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими снаружи от цикла <tex>C</tex>.}}{{Определение|definition =<b>Внешними компонентами</b> (англ. ''Outside components'') будем называть компоненты связности внешнего графа.}}В силу связности графа <tex>G'</tex> для любой внешней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.{{Определение|definition =<b>Внешними частями</b> (англ. ''Outside parts'') будем называть внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами , либо рёбра графа <tex>G'</tex>, лежащие снаружи от цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами.}}[[Файл:nb.pic.7.png|440px|рис. 7]]{{Определение|definition =<b>Внутренним графом</b> (англ. ''Inside graph'') (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими внутри цикла <tex>C</tex>.}}{{Определение|definition =<b>Внутренними компонентами</b> (англ. ''Inside components'') будем называть компоненты связности внутреннего графа.}}В силу связности графа <tex>G'</tex> для любой внутренней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.{{Определение|definition =<b>Внутренними частями</b> (англ. ''Inside parts'') будем называть внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами, либо рёбра графа <tex>G'</tex>, лежащие внутри цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами}}Будем говорить, что внешняя (внутренняя) часть ''встречает цикл'' <tex>C</tex> в своих точках прикрепления к циклу <tex>C</tex>.{{Лемма|about=1|statement =Любая внешняя часть встречает цикл <tex>C</tex> точно в двух точках, одна из которых лежит в <tex>C(a,b)</tex>, а другая {{---}} в <tex>C(b,a)</tex>.|proof = Если внешняя часть встречает цикл <tex>C</tex> точно в одной точке <tex>v</tex>, то <tex>v</tex> является точкой сочленения графа <tex>G</tex>, что невозможно. [[Файл:nb.pic.8.png|420px|рис. 8]] Таким образом, внешняя часть встречает цикл <tex>C</tex> не менее чем в двух точках. Если внешняя часть встречает цикл <tex>C</tex> в двух точках из <tex>C[a,b]</tex> (случай <tex>C[b,a]</tex> рассматривается аналогично), то в <tex>G'</tex> имеется цикл, содержащий внутри себя больше граней, чем цикл <tex>C</tex>, и проходящий через <tex>a</tex> и <tex>b</tex>, что невозможно. [[Файл:nb.pic.9.png|420px|рис. 9]] Итого, внешняя часть встречает цикл <tex>C</tex> хотя бы в двух точках, никакие две из которых не лежат в <tex>C[a,b]</tex> и <tex>C[b,a]</tex>. То есть ровно одна лежит в <tex>C(a,b)</tex> и ровно одна {{---}} в <tex>C(b,a)</tex>.}}{{Определение|definition =Ввиду леммы 1 будем говорить, что любая внешняя часть является <b><tex>(a,b)</tex> {{---}} разделяющей частью</b> (англ. ''separating part''), поскольку она встречает и <tex>C(a,b)</tex>, и <tex>C(b,a)</tex>.}} Аналогично можно ввести понятие <tex>(a,b)</tex> {{---}} разделяющей внутренней части. Заметим, что внутренняя часть может встречать цикл <tex>C</tex>, вообще говоря, более чем в двух точках, но не менее чем в двух точках.{{Лемма|about=2|statement = Существует хотя бы одна <tex>(a,b)</tex> {{---}} разделяющая внутренняя часть.|proof =Пусть, от противного, таких частей нет. Тогда, выходя из <tex>a</tex> внутри области, ограниченной <tex>C</tex>, и двигаясь вблизи от <tex>C</tex> по направлению обхода <tex>C</tex> и вблизи от встречающихся внутренних частей, можно уложить ребро <tex>e = ab</tex> внутри цикла <tex>C</tex>, т.е. <tex>G</tex> {{---}} планарный граф, что невозможно. [[Файл:nb.pic.10.png|280px|рис. 10]] }}{{Лемма|about=3|statement =Существует внешняя часть, встречающая <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> [[Файл:nb.pic.11.png|240px|рис. 11]] |proof =Пусть, от противного, лемма 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>. [[Файл:nb.pic.12.png|310px|рис. 12]] Поскольку на участках <tex>C(u_{1},u_{2})</tex> и <tex>C(v_{1},v_{2})</tex> нет точек прикрепления внешних частей, используя жорданову кривую <tex>P</tex>, внутреннюю часть <tex>In_{1}</tex> можно перебросить ("вывернуть" наружу от цикла <tex>C</tex>) во внешнюю область цикла <tex>C</tex>, т.е. уложить её снаружи от цикла <tex>C</tex> и сделать её внешней частью.Аналогично все остальные <tex>(a,b)</tex> {{---}} разделяющие внутренние части можно перебросить во внешнюю область от цикла <tex>C</tex>. После этого точно так же, как в доказательстве леммы 2, ребро <tex>e = ab</tex> можно уложить внутри цикла <tex>C</tex>, так как не останется <tex>(a,b)</tex> {{---}} разделяющих внутренних частей. Следовательно, мы получим укладку графа <tex>G</tex>, что невозможно.}}  == Разбор случаев взаимного положения вершин ''a, b, c, d, u1, u2, v1, v2'' ==* Пусть пара вершин <tex>\ v_1 </tex> и <tex>\ v_2 </tex> <b> является </b> <tex>(a, b)</tex> {{---}} разделяющей. <br>*: Тогда, в частности, <tex>v_2 \ne a</tex> и <tex> v_1 \ne b</tex>. *: В этом случае граф <tex>G</tex> содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex> {{---}} цепь). ;: [[Файл:Case_1.png|270px|рис. 7.1]] * Пусть пара вершин <tex>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|200px|рис. 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|200px|рис. 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.2.3.png|200px|рис. 7.8]]*#:<br>*#:<br>*# <b> Пусть <tex>v_2 = a</tex>.<br> </b>*#:[[Файл:Сase_2.3(a).png|200px|рис. 7.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.3(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|200px|рис. 7.11]]*## Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>*##: Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_5</tex>.<br>*##: [[Файл:Сase_2.3.2.png|200px|рис. 7.12]] Таким образом, доказано, что в графе <tex>G </tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br>}} == См. также ==* [[Двойственный граф планарного графа]]* [[Теорема Фари]] == Примечания ==<references /> ==Источники информации==* [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)] * Асанов М., Баранский В., Расин В. {{---}} Дискретная математика {{---}} Графы, матроиды, алгоритмы [[Категория: Алгоритмы и структуры данных]][[Категория: Укладки графов ]]