Изменения

Заметим, что из планарности графа следует планарность гомеморфного гомеоморфного графа и наоборот. В самом деле, пусть <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 — {{---}} обыкновенный граф ===

=== G — {{---}} [[Отношение_вершинной_двусвязности|блок]] ===

<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> {{---}} планарны. [[Файл:New.nb.pic.1.png|400px|рис. 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> будет представлена на плоскости в двух экземплярах. [[Файл:nb.pic.2.png|400px|рис. 2]]

В силу минимальности Соединим два экземпляра вершины <tex> G v </tex>пучком жордановых линий, не допуская лишних пересечений с укладками графов <tex> G_1 </tex> и <tex> G_2 </tex> - планарны.[[Файл:New.p-k.1.png|thumb|right|рис. 1]]Возьмём укладку графа , состоящим из такого количества линий, какова степень вершины <tex> G_1 v </tex> на плоскости такую, что вершина в графе <tex> v G_2 </tex> лежит на границе внешней грани. Ее можно получить, взяв любую укладку Далее отбросим вхождение вершины <tex> G_1 v </tex> на плоскости, по ней построив укладку на шаре, используя обратную [http://en.wikipedia.org/wiki/Stereographic_projection стереографическую проекцию], потом повернуть сферу так, чтоб в граф <tex> v G_2 </tex> оказалась , заменяя инцидентные ей рёбра на внешней грани стереографической проекции повернутого шаражордановы линии, полученные из линий указанного пучка и рёбер. [[Файл:nb.pic.3.png|400px|рис. 3]]

Пусть <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> 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]] 

Среди всех укладок графа <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>.

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

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

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

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

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

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

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

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

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

 [[Файл:pict-4nb.pic.9.jpgpng|center420px|рис. 109]] Итого, внешняя часть встречает цикл <tex>C</tex> хотя бы в двух точках, никакие две из которых не лежат в <tex>C[a,b]</tex> и <tex>C[b,a]</tex>. То есть ровно одна лежит в <tex>C(a,b)</tex> и ровно одна {{--- }} в <tex>C(b,a)</tex>.

Ввиду леммы 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>, вообще говоря, более чем в двух точках, но не менее чем в двух точках.

2) Существует хотя бы одна <tex>(a,b)</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.pic.10.jpg|centerpng|180px280px|рис. 1110]] 

3) Существует внешняя часть, встречающая <tex>C(a,b)</tex> в точке <tex>c</tex> и <tex>C(b,a)</tex> — {{---}} в точке <tex>d</tex>, для которой найдётся внутренняя часть, являющаяся одновременно <tex>(a,b)</tex>{{-разделяющей и <tex>(c,d)</tex>-разделяющей.[[Файл:pict-6.jpg|center|160px|рис. 12]]|proof =Пусть, от противного, лемма 3 неверна. Упорядочим <tex>(a,b)</tex>-разделяющие внутренние части в порядке их прикрепления к циклу <tex>C</tex> при движении по циклу от <tex>a</tex> до <tex>b</tex> и обозначим их соответственно через <tex>In_{1},In_{2},...</tex> Пусть <tex>u_{1}</tex> разделяющей и <tex>u_{2}</tex> — первая и последняя вершины из <tex>C(ac,bd)</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-7.jpg|center|200px|рис. 13]]Поскольку на участках <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</texbr> и сделать её внешней частью.Аналогично все остальные <tex>(a,b)</tex>-разделяющие внутренние части можно перебросить во внешнюю область от цикла <tex>C</tex>. После этого точно так же, как в доказательстве леммы 2, ребро <tex>e = ab</tex> можно уложить внутри цикла <tex>C</tex>, так как не останется <tex>(a,b)</tex>-разделяющих внутренних частей. Следовательно, мы получим укладку графа <tex>G</tex>, что невозможно.}}

|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>, cв которых <tex>In_{1}</tex> встречает цикл <tex>C</tex>, dа <tex>v_{1}</tex> и <tex>v_{2}</tex> {{---}} первая и последняя вершины из <tex>C(b, u1a)</tex>, u2в которых <tex>In_{1}</tex> встречает цикл <tex>C</tex> (возможно, v1вообще говоря, v2'' <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[Файл:Case_1u_{2},v_{1}]</tex>.png|thumb|right|рисТогда снаружи цикла <tex>C</tex> можно провести жорданову кривую <tex>P</tex>, не пересекая рёбер графа <tex>G'</tex>, соединяющую <tex>v_{2}</tex> с <tex>u_{1}</tex>. 7.1]]

1[[Файл:nb. Пусть пара вершин <tex>\ v_1 </tex> и <tex>\ v_2 </tex> является <tex>(a, b)</tex>-разделяющейpic. <br>Тогда, в частности, <tex>v_2 \ne a</tex> и <tex> v_1 \ne b</tex>12. В этом случае граф <tex>G</tex> содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>-цепь) (png|310px|рис. 7.1).12]]

Поскольку на участках <tex>C(u_{1},u_{2. Пусть пара вершин })</tex> и <tex>v_1C(v_{1},v_{2})</tex> и нет точек прикрепления внешних частей, используя жорданову кривую <tex>v_2P</tex> не является , внутреннюю часть <tex>In_{1}</tex>можно перебросить (a, b)"вывернуть" наружу от цикла <tex>C</tex>-разделяющей. ) во внешнюю область цикла <brtex>Тогда C</tex>v_1, v_2т.е. уложить её снаружи от цикла <tex>C</tex> лежат на и сделать её внешней частью.Аналогично все остальные <tex>C[(a, b])</tex> или на {{---}} разделяющие внутренние части можно перебросить во внешнюю область от цикла <tex>C[b, a]</tex>. Без ограничения общности будет считатьПосле этого точно так же, что как в доказательстве леммы 2, ребро <tex>v_1e = ab</tex> и можно уложить внутри цикла <tex>v_2C</tex> лежат на , так как не останется <tex>C[(a, b])</tex>{{---}} разделяющих внутренних частей.Следовательно, мы получим укладку графа <brtex>G</tex>, что невозможно.}}

2.1.1 == Разбор случаев взаимного положения вершин ''a, b, c, d, u1, u2, v1, v2'' ==* Пусть пара вершин <tex>u_2\ v_1 </tex> лежит на и <tex>\ v_2 </tex> <b> является </b> <tex>C(da, ab)</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> (рис. 7.3v_1, v_2).<br/tex>{{---}} цепь).

2;: [[Файл:Case_1.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>. В этом случае в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (png|270px|рис. 7.4).<br>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.59]]*#:Рассмотрим теперь пару вершин <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]]

<center><gallery style="text-align:center; font-size:90%" >Файл:Сase_2.1.png|рис. 7.2Файл:Сase_2.1.1.png|рис. 7.3Файл:Сase_2.1.2.png|рис. 7.4Файл:Сase_2.1.3.png|рис. 7.5</gallery></center> Теперь рассмотрим случаиТаким образом, когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>. Без ограничения общности будем считатьдоказано, что это вершина в графе <tex>v_1G</tex>имеется подграф, т.е гомеоморфный <tex>v_1 = bK_{3,3}</tex>(поскольку или <tex>v_1K_5</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>также ==* [[Двойственный граф планарного графа]]Тогда в графе <tex>G</tex> есть пограф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.6).<br>* [[Теорема Фари]]

2.2.2. Пусть <tex>u_2 = d</tex>.<br>= Примечания ==Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}<references /tex> (рис. 7.7).<br>

2.2.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.8). <br> <center><gallery style="text-align:center; font-size:90%" >Файл:Сase_2.2.1.png|рис. 7.6Файл:Сase_2.2.2.png|рис. 7.7=Источники информации==Файл* [https:Сase_2.2.3.png|рис. 7.8</gallery></center> 2.3. Пусть <tex>v_2 = a</tex> (рис. 7ru.9)wikipedia.<br>Рассмотрим теперь пару вершин <tex>u_1<org/tex> и <tex>u_2<wiki/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> (рис. 7.10).}} Планарный граф]Заметим, что <tex>P_1<* [http:/tex> и <tex>P_2</tex> имеют общую точку.<br> 2.3en.1wikipedia. Пусть цепи <tex>P_1<org/tex> и <tex>P_2<wiki/tex> имеют более одной общей точки.<br>Kuratowski's_theorem Wikipedia {{---}} Kuratowski's theorem]Тогда в графе <tex>G<* [http:/tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex> (рисacm. 7math.11)spbu.<br> 2.3.2. Пусть цепи <tex>P_1</tex> и <tex>P_2<ru/tex> имеют точно одну общую точку <tex>w<~sk1/tex>.<br>Тогда в графе <tex>G<download/tex> есть подграф, гомеоморфный <tex>K_5<books/tex> (рис. 7.12)TheoremKuratowski.<br> <center><gallery style=pdf "text-align:center; font-size:90%Вокруг критерия Куратовского планарности графов" >Файл:Сase_2.3(a).png|рис. 7.9Файл:Сase_2стр.3(b118).png|рис. 7.10] Файл:Сase_2* Асанов М.3, Баранский В.1, Расин В.png|рис. 7.11Файл:Сase_2.3.2.png|рис. 7.12</gallery></center> Таким образом, доказано, что в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3{---}}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br> Дискретная математика {{---}} Графы, матроиды, алгоритмы