Изменения

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

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

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

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

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

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

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

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

5) Любая внешняя часть встречает цикл <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>, что невозможно.Таким образом, внешняя часть встречает цикл <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>, что невозможно.Итого, внешняя часть встречает цикл <mathtex>C</mathtex> хотя бы в двух точках, никакие две из которых не лежат в <mathtex>C[a,b]</mathtex> и <mathtex>C[b,a]</mathtex>. То есть ровно одна лежит в <mathtex>C[a,b]</mathtex> и ровно одна - в <mathtex>C[b,a]</mathtex>.

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

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

6) Существует хотя бы одна <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> - планарный граф, что невозможно.

{{Утверждение 7Теорема

7) Существует внешняя часть, встречающая <mathtex>C(a,b)</mathtex> в точке <mathtex>c</mathtex> и <mathtex>C(b,a)</mathtex> - в точке <mathtex>d</mathtex>, для которой найдётся внутренняя часть, являющаяся одновременно <mathtex>(a,b)</mathtex>-разделяющей и <mathtex>(c,d)</mathtex>-разделяющей.

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