Изменения

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

Если внешняя часть встречает цикл <tex>C</tex> точно в одной точке <tex>v</tex>, то <tex>v</tex> является точкой сочленения графа <tex>G</tex>, что невозможно (см. рис. 9).

Таким образом, внешняя часть встречает цикл <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>, что невозможно (см. рис. 10).

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

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>-разделяющей (см. рис. 12).

Пусть, от противного, лемма 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(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> (см. рис. 13).

[[Файл:Case_1.png|thumb|right|рис. 7. 1]]

Тогда, в частности, <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>-цепь) (рис. 7. 1).

2.1. Пусть <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> (рис. 7. 2). <br>

Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7. 3).<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> (рис. 7. 4).<br>

Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7. 5).<br>

Файл:С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

Тогда в графе <tex>G</tex> есть пограф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7. 6).<br>

Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7. 7).<br>

Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7. 8). <br>

Файл:Сase_2.2.1.png|рис. 7. 6Файл:Сase_2.2.2.png|рис. 7. 7Файл:Сase_2.2.3.png|рис. 7. 8

2.3. Пусть <tex>v_2 = a</tex> (рис. 7. 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> (рис. 7. 10).

Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7. 11).<br>

Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_5</tex> (рис. 7. 12).<br>

Файл:Сase_2.3(a).png|рис. 7. 9Файл:Сase_2.3(b).png|рис. 7. 10Файл:Сase_2.3.1.png|рис. 7. 11Файл:Сase_2.3.2.png|рис. 7. 12