23
правки
Изменения
Нет описания правки
==== Разбор случаев взаимного положения <tex>''a, b, c, d, u1, u2, v1, v2</tex> '' ====
Рассмотрим 2 случая.
[[Файл:Case_1.png|thumb|right|рис. 1]]
----
1. Пусть пара вершин <tex>\ v_1 </tex> и <tex>\ v_2 </tex> является <tex>(a, b)</tex>-разделяющей. <br>
Тогда, в частности, <tex>v_2 \ne a</tex> и <tex> v_1 \ne b</tex>. В этом случае граф G содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>-цепь)(рис. 1).
----
2. Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> не является <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>
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>(рис. 2). <br><br>[[Файл:Case_2.1.png|thumb|right|рис. 2]]
2.1.1 Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
Тогда в графе G имеется подграф, гомеоморфный <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_2.1.2.png|thumb|right|рис. 4]]
2.1.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
Тогда в графе G есть подграф, гомеоморфный <tex>K{3,3}</tex>(рис. 5).<br> <brp>[[Файл:Сase_2.1.png|150px|рис. 2]][[Файл:Сase_2.1.1.png|150px|рис.3]][[Файл:Сase_2.1.2.png|thumb150px|rightрис. 4]][[Файл:Сase_2.1.3.png|150px|рис. 5]]</p> ----
Теперь рассмотрим случаи, когда хотя бы одна из вершин <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>
2.2. Пусть <tex>v_2 \ne a</tex>.<br><br>
2.2.1. Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
Тогда в графе G есть пограф, гомеоморфный <tex>K_{3,3}</tex>(рис. 6).<br><br>[[Файл:С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_2.2.1.png|thumb|right|рис. 7]]
2.2.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 8). <br><brp>[[Файл:Сase_2.2.1.png|150px|рис. 6]][[Файл:Сase_2.2.2.png|thumb150px|rightрис. 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).
2.3.1. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>
Тогда в графе G есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 11).<br><br>[[Файл:Сase_2.3.1.png|thumb|right|рис. 11]]
2.3.2. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>
Тогда в графе G есть подграф, гомеоморфный <tex>K_5</tex>(рис. 12).<br> <brp>[[Файл:С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|thumb|right150px|рис. 12]]</p>
Таким образом, доказано, что в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br>
