Содержание к диссертации
Введение
Связность 3
Структура разбиения /с-связного графа 5
Результаты диссертации 8
Ромашки в / -связном графе 11
Ромашки в четырехсвязном графе 13
Структура диссертации 15
1 Обобщенные ромашки в /с-связном графе 17
2 Ромашки в четырехсвязном графе 56
2.1 2-Ромашки 56
2.2 О-Ромашки
- Структура разбиения /с-связного графа
- Результаты диссертации
- Ромашки в четырехсвязном графе
- в четырехсвязном графе
Структура разбиения /с-связного графа
Расположим индексы 1, 2,..., m по окружности соответственно их циклическому порядку и поставим в соответствие множеству Qij хорду этой окружности, соединяющую і и j. Тогда внутренние множества QXiV и QZit ромашки F являются зависимыми к-разделяющими множествами в том и только том случае, когда соответствующие им хорды окружности пересекаются во внутренней точке. 2) Если множества QXiV и Qz t являются зависимыми разделяющими множествами, то QXiV отделяет друг от друга лепестки Qz и Qt Доказательство этих утверждения непосредственно следует из теоремы 1.
Из теоремы 1 следует, что для неблизких лепестков і и j подграфы Gij и Gjyi можно понимать как обобщенные части, на которые Qij делит граф G. Соответственно, для них применимы определения границы и внутренности. Кроме того, подграфы G +i мы называем частями разбиения графа G ромашкой. Далее для удобства все подграфы Gij, где і = j, мы будем называть частями даже если ( и Qj являются близкими, но не соседними (на самом деле, в этом случае подграф Gij является обобщенной частью разбиения графа G обобщенной ромашкой, получающейся из F удалением всех лепестков с номерами от і до j, но мы не будем на этом останавливаться). Для подграфа Gij определим понятие внутренности и границы, а также укажем, когда мы будем называть его пустой частью, а когда — малой.
Определение 17. Пусть F = (Р; Qi, , Qm) — обобщенная ромашка, Part(F) = {Gi;2, ..., Стод}. Для неравных і и j введем понятия границы и внутренности Gij. Границей Gij называем Bound(() = Qij, а внутренностью — Int (Gij) = У (Gij — Qij). Соответственно, назы ваем часть Gij пустой, если у нее пустая внутренность и малой, если \V(Ghj)\ к.
Лемма 1.4. Для обобщенной ромашки F = (Р; Q\,..., Qm) верно следующее. 1) Если ни один из лепестков не лежит в объединении остальных, то R(F) состоит просто из множеств Qij для всех пар различных несоседних в циклическом порядке индексов і и j. 2) Если лепестки Qi и Qj являются близкими, но не соседними, то одна из частей Gij и Gj пуста. Доказательство. 1) Заметим, что если два лепестки являются близкими, но не соседними, то в их объединении должен содержаться как минимум один лепесток. Поэтому если ни один из лепестков ромашки не лежит в объединении остальных, то близкими являются только соседние лепестки. А набор R(F) состоит как раз из множеств вида Qi,j, где лепестки Qi и Qj не являются близкими. 2) Если Qi и Qj пересекаются, то это просто пункт 2) леммы 1.2. Теперь предположим, что они не пересекаются. Так как эти лепестки — несоседние, между ними с обеих сторон есть лепестки. Но они являются близкими, поэтому хотя бы с одной из сторон лепестки, лежащие между ними, целиком содержатся в Qij. Не умаляя общности считаем, что это лепестки с номерами от і до j. Рассмотрим Qi+\. Этот лепесток лежит в Qij. Поэтому он обязан пересекаться и с Qi, и с Qj. Тогда по второй части леммы 1.2 одна из частей G +i и Gi+\ является пустой. Ясно, что пуста именно G j+i, так как в Gi+\ есть некоторое количество вершин из Qj, не лежащих в Qi;b+\. Аналогично доказываем, что Gj+ij пуста. Так как V(Gij) = V(Gi,»+i) U V(Gi+ij) и Qi+i с Qi}j, получаем требуемое.
Лемма 1.5. Пусть набор разделяющих множеств & порождает обобщенную ромашку F. Известно, что вершина и содержится в каждом из множеств набора @. Тогда и лежит в центре ромашки F.
Доказательство. Предположим, что вершина и не лежит в центре ромашки F. Ясно, что и есть в границе каждой из частей разбиения графа G набором @. Тогда для любого г знаем, что либо и Є Qi либо и Є Qi+i- Теперь предположим, что нашлись два лепестка Qi и Qj, не содержащие и. Ясно, что они не могут быть соседними. Разберем два случая.
Случай 1. Лепестки Qi и Qj близки. Тогда по лемме 1.4 одна из частей Gij и Gjj пуста, то есть совпадает с Qij. Пусть это часть Gij. Тогда Qi,i+i С Q j. Но и . Qij, а один из лепестков Qi и Q«+i обязан содержать и. Противоречие.
Случай 2. Лепестки Qi и Qj не близки. Тогда по теореме 1 множество Qij отделяет Gij от Gjj. Но при этом вершина и есть и в той, и в другой части, а в Qij ее нет. Противоречие. Значит, нет двух лепестков, не содержащих и. Заметим, однако, что любое множество Т Є & является множеством вида Qij, где Qi и Qj — это два непересекающихся лепестка. В частности, в составе любого Т Є & есть лепесток, не содержащий и. Но у нас среди лепестков ромашки F найдется не более, чем один такой. Таким образом, он есть, и все множе ства из & содержат его как один из двух образующих лепестков. Выберем любую вершину v этого лепестка и проведем для нее то же самое рассуж дение. Получим, что найдется некий другой лепесток, который участвует в образовании всех множеств из &. Значит, набор & состоит из одного множества. Противоречие. Лемма 1.6. Пусть два несоседних лепестка Qi и Qj обобщенной ромашки F пересекаются, причем именно часть Gij является пустой. Тогда имеет место следующее включение множеств: Яг П Ql+l Э Q% П Яг+2 Э Э Q% П Qj. Доказательство. Докажем, что для любого А; от і до j есть включение Qk 1Э QiDQj. Пусть это не так. То есть нашлись такие вершина и Є QiHQj и номер А; от і до j, что и Qk- Рассмотрим произвольный лепесток Qg: для которого не равно ни одному из i/i + 1,..., j. Докажем, что все такие лепестки содержат вершину и. Разберем два случая. Случай 1. Лепестки Qi и Qk близки. Тогда либо Qi С ( либо Qj С Q k-Так как и Є Qi П Qj, в любом случае получаем, что и Є Q k- Но и . Qk-Значит, и Є Qi. Случай 2. Лепестки Qi и Qk не близки. Тогда по теореме 1 множество Qi k отделяет G( k от Gk/. Но при этом вершина и есть и в той, и в другой части. Значит, она должна быть и в (. Теперь рассмотрим любое множество Т Є &. Заметим, что максимум один из двух лепестков, образующих Т, находится среди Qi,Qi+i,- ,Qj, так как любые два лепестка из этой группы пересекаются. Значит, для любого Т Є в найдется такое , не равное ни одному из і, і + 1, ..., j, что Qi С Т. Но мы доказали, что все такие лепестки содержат вершину и. Тогда и любое множество из набора & содержит и. По лемме 1.5 получаем, что и Є Р и приходим к противоречию.
Результаты диссертации
Теперь рассмотрим множества вида Qij: имеющиеся в наборе (5. Мы их заменяем на множества Sj: то есть вершину х заменяем нам, а у — на v. При этом с обобщенными частями происходит то же самое — в одной из них х заменяется на и, а в другой — у на v. При этом в первой либо есть обе вершины у и -и, либо нет ни одной из них, а во второй — либо есть обе вершины жим, либо нет ни одной из них.
Из всего этого можно сделать следующий вывод — если мы во всех множествах набора и их обобщенных частях заменим х на и, а и на ж, и у на -и, a v на у, то получим множества набора & и их обобщенные части. Поэтому, если первый набор определяет обобщенную ромашку F, то второй — обобщенную ромашку F : у которой те же лепестки, что и у F, только вместо Qi берется Q i: и те же части разбиения, только вместо Gi-\ и Gi +\ получаются G({x,u,v}) и G({u,v,y}), соответственно.
Рис. 2.1: Похожие ромашки объединение каких-то двух лепестков F, то Т является либо внутренним множеством F, либо ее границей. Также ясно, что Т заведомо лежит в объединении некоторых четырех лепестков F. Разберем два случая. Случай 1. Т можно покрыть тремя лепестками F. Не умаляя общности, считаем, что Т содержит обе вершины лепестка Q\ и по одной вершине лепестков Qi и Qj, где і от 1 до j. Заметим, что по лемме 1.9 либо граф G\ i — Т связен, либо V(Gi ) С Т. Кроме того, лепесток ( может содержаться целиком в Т, только если V(Gi;j) С Т. Поэтому если граф V(Gi i) . Т, то у подграфов G\ — Ти Gij — Т есть общая вершина. То же можно сказать про G \ — Т. Тогда граф Gij — Т не может быть связным (так как иначе G — T связен). Предположим, что Gij непуста. Применим лемму 1.9, получим, что граф Gij — Т связен и придем к противоречию.
Значит, часть Gij все же пуста, причем либо граф Gij — Т обязан быть несвязным, либо V(Gij) С Т. Но если V(Gjj) С Т, то часть Gij пуста, и каждый из лепестков Qi и Qj обязан пересекаться с Qi, из чего следует, что части G\ и G \ обе являются малыми, а это невозможно (тогда в графе всего четыре вершины). Поэтому граф Gij — Т обязан быть несвязным, и в нем, следовательно, должно быть по крайней мере две вершины. Тогда в Gij — Т есть ровно две вершины — как раз те вершины лепестков Qi и Qj, которые не входят в Т. Если T\Qi является лепестком F, то все в порядке. Предположим, что это не так. Пусть Qi = {и,х}, Qj = {v,y}, Т Г) Qi = {и}, а Т П Qj = {v}. Заметим, что из доказанного выше следует, что Part(T) = {G(V(Gi i) U {v}),G(V(Gj:i) U {и})}. Поэтому, если Qi и Qj являются соседними лепестками, то можно добавить к F лепесток {и, -и}, а к порождающему набору — множество Т, что противоречит максимальности F.
Тогда лепестки Qi и Qj не являются соседними, но при этом Gij пуста. Значит, j = і + 2, и обе части G +i и СІ+І,І+2 ЯВЛЯЮТСЯ малыми. Заметим, что Q«+i ф { ,у}, так как иначе по лемме 2.3 вершины х и у должны быть смежны, а это не так. Аналогично Q«+i ф {v,x}. Поэтому лепесток Qi+i = {ж, у} и является переключателем, причем при его переключении он переходит в Т \ Qi: а ромашка F — в ромашку F : похожую на нее. Ясно, что Т является внутренним множеством F (граничным оно являться, очевидно, не может), то есть квазивнутренним множеством ромашки F.
Случай 2. Т нельзя покрыть тремя лепестками F. Пусть Т содержит по одной вершине лепестков Qi,Qi,Qj ttQk,i j к. Введем обозначения — для произвольных индексов и m возьмем H m = G m — Т. Заметим, что по лемме 1.9 граф Ні І несвязен, только если часть G\ пуста. Причем в этом случае Ні І — это две несмежные вершины. Аналогично для -/, - и #jfe,l. Предположим, что какие-то два соседних из них являются несвязными — пусть это Hj и Hk,\. Но тогда вершина из Qk-, не входящая в Т, может быть соединена лишь с тремя вершинами (это все вершины Т кроме той, что лежит в Qi): что противоречит четырехсвязности графа G.
Теперь предположим, что какие-то два соседних из них являются связными — пусть это Ні І и Hij. Тогда H\j — тоже связен. В таком случае G — Т будет несвязен, только если оба подграфа Hj и Hj ,i несвязны, а такого, как мы только что доказали, не бывает. Значит, можно считать, что подграфы Ні І И HJ несвязны, а под графы Hij и Hk,\ связны. Ясно, что тогда компонентами связности в гра фе G — Т будут как раз подграфы Н и Н \. Пусть Qk П Т = {и}, a Qj\T = {v}. Заметим, что множество Q\j разбивает граф G на обоб щенные части Gij и С д, поэтому вершина и может быть смежна только с одной вершиной графа Hij — с вершиной v. Поэтому S = Т U {v} \ {и} отделяет и от V(Hij). Так как S нельзя покрыть двумя лепестками ро машки F, но можно тремя, из доказательства случая 1 следует, что S\Qj является лепестком F ИЛИ ромашки, похожей на F. Но при этом ясно, что S\Qj = ТП (Qi UQi). Аналогично для ТП (( UQk) Поэтому Т является квазивнутренним.
Теперь перейдем к описанию взаимного расположения двух максимальных обобщенных 0-ромашек. В итоговой теореме появятся некоторые исключения — ромашки специального вида, в каждом из исключений не более семи лепестков. Начнем исследование свойств этих исключений. Лемма 2.5. Пусть все лепестки обобщенной 0-ромашки F пересекаются с Qij, где Qi и Qj — это два ее неблизких лепестка. Тогда лепестков в ромашке F ровно 6, j = і + 3; і = j + 3; лепестки Qi-\ и Qi+\ пересекаются с Qi, a Qj-i и Qj+i — с Qj. При этом части Gi-\ , Gi +\, GJ-IJ, Gjj+i являются малыми, и каждая вершина из Qij лежит ровно в двух лепестках.
Доказательство. По лемме 2.3 пересекаться в 0-ромашке могут только соседние лепестки. Заметим, что тогда в каждой из частей Gij и Gj лежит не более, чем по два лепестка Предположим, что в части Gij лежит ровно один лепесток (хотя бы один быть должен, иначе Qi и Qj будут соседними). Тогда это лепесток Qi+i, и j = і + 2. Не умаляя общности, считаем, что он пересекается с Qi. Теперь рассмотрим лепесток, не близкий к Qi+i — по лемме 1.2 такой есть. Ясно, что по лемме 2.3 он не может пересекаться с Qi. Значит, он пересекается с Qiyi. Тогда это Qiy. Пусть общая вершин Qiyi и Qiy — это вершина х. Рассмотрим разделяющее множество, не содержащее х. Оно должно состоять из двух неблизких лепестков, ни один из которых не совпадает ни с Qi+i, ни с Qiy. Но кроме них в F есть только лепестки Qi, Qi+i и, возможно, лепесток Qi-l: который в таком случае должен пересекаться с Qi. В любом случае выбрать пару неблизких из них не получится. Противоречие.
Ромашки в четырехсвязном графе
Из доказанного выше (см. вывод 2) следует, что вершины лепестка Qi не лежат в V(F ). Предположим, что нашелся лепесток ромашки F : делящий часть G[ (которая, напомним, совпадает с Gi ) на две непустые. Тогда все вершины из V(F), лежащие в части G\ , содержатся в V(F ) (см. вывод 7). Но Qi (/і V(F ). Противоречие.
Значит, для любого лепестка Q x ромашки F , где ж от 1 до j, одна из частей G i х и G x пуста. Ясно, что тогда все вершины непустого множества V(F) \ V(F ) в части G\ находятся во внутренности некоторой одной общей для всех них части разбиения графа G ромашкой F (надо взять либо G l2) если G 2j пуста, либо G -_1, если G x _x пуста, либо G xx+1, где части G lx и G x+1j пусты). Значит, по первой части леммы 1.9 ни одно из внутренних множеств ромашки F не разделяет множество (V(F) \ V(F )) П V(Gi;j), причем даже не в смысле обобщенных частей, а в смысле обычных.
Если в части G \ нашелся лепесток ромашки F, делящий эту часть на две непустые, то все вершины ромашки F : лежащие в С,ц, являются вершинами ромашки F (см. вывод 7). Это невозможно, так как мы знаем, что все вершины ромашки F : лежащие в G\ , являются вершинами ромашки F, поэтому если тоже самое выполнено и для части б д, то V(F ) С V(F), причем V(F ) 7 V(F), что противоречит максимальности ромашки F .
Пусть в части G \ нашелся лепесток F : делящий эту часть на две непустые. Тогда вершины из V(F), лежащие в части б д, содержатся в y(F ) (см. вывод 7). Значит, аналогично доказанному выше, никакое внутреннее множество ромашки F не разделяет множество вершин V(F ) \ V(F), лежащих в части б д. Итак, в части G\ нет вершин множества V(F ) \ V(F), и ни одно внутреннее множество ромашки F не разделяет V(F)\V(F ), а в части G \ нет вершин множества V(F)\V(F ), и ни одно внутреннее множество ромашки F не разделяет V(F ) \ V(F). Тогда это утверждение верно и глобально в графе G для обеих ромашек — ни одно внутреннее множество ромашки F не разделяет V(F) \ V(F ), и ни одно внутреннее множество ромашки F не разделяет V(F ) \ V(F). Противоречие.
Вывод 8. Если в одной из частей G\ и G \ нашелся лепесток F, делящий эту часть на две непустые, то возможны следующие варианты: граф является одним из исключений (см. рис. 2.4); все вершины ромашки F : содержащиеся в этой части, являются вершинами ромашки F, и при этом ни одно внутреннее множество F не разделяет множество вершин V(F) \ V(F ), содержащихся в этой части.
Аналогично для F . Поэтому в случае, когда в обеих частях G\ и G \ есть лепестки одной из ромашек F и F : делящие соответствующую часть на две непустые и не пересекающиеся с Qij, получается, что граф G — одно из исключений. Теперь посмотрим, каким же образом внутреннее множество ромашки F, например, может разделять V(F ) \ V(F). Докажем, что ни одно внутреннее множество F не может разделять (V(F ) \ V(F)) П V(Gi;j). Пусть такое множество нашлось. Ясно, что тогда множество V(F) не содержит всех вершин ромашки F : содержащихся в части G\ . Поэтому точно нет лепестков ромашки F, делящих часть G\ на две непустые. Значит, множество вершин (V(F ) \ V(F)) П V(Gi;j), целиком лежит во внутренности одной из частей разбиения графа G ромашкой F, и поэтому не разделяется ни одним внутренним множеством F. Аналогичное утверждение верно и для части G \.
Вывод 9. Если некое внутреннее множество ромашки F разделяет множество V(F ) \ V(F), то оно обязано разделять его на две части, одна из которых содержится в части Сід, а другая — в б д. Тогда в обеих частях бгід и Gj;i должны найтись вершины ромашки F : не являющиеся вершинами ромашки F. Поэтому ни в одной из этих частей нет лепестков ромашки F, делящих эту часть на две непустые.
Значит, по лемме 2.7 между лепестками Q[ и Q - нет ребер. Таким образом, вершины s,t,u,v попарно не смежны. Заметим, что оба лепестка Q x и Q y одновременно не могут разбивать части G\;b и G \ соответственно на две непустые, так как иначе V(F) содержалось бы строго внутри V(F ), что невозможно (см. вывод 8). Теперь разберем несколько случаев в зависимости от наличия лепестков ромашки F, не пересекающихся с Q\ . В каждом из них мы, в частности, докажем, что ни один из лепестков Q x и Q не может разбивать соответствующую часть на две непустые.
В какой-то из частей G\;b и G \ есть лепестки F, не пересекающиеся с Q\;b. Не умаляя общности, считаем, что такие лепестки есть в части G\ . Рассмотрим один из них в этой части. Пусть это лепесток Qg = {di,d,2} (см. рис. 2.14). Как уже было доказано (см. вывод 9), одна из частей G\i9 и Gg;b пуста. Не умаляя общности, будем считать, что пуста именно часть G\i9.
Предположим, что Q x разбивает часть G\ на две непустые. Заметим, что из доказанного выше (см. вывод 2) следует, что ни один из лепестков F, содержащихся в G\ , не может пересекаться с Q x. В част Q, ности, ни одна из вершин d\ и d i не содержится в Q x. Ясно, что s и t могут быть смежны только с d\ и d i в Сі,«, так как п0 лемме 1.10 лепесток Qg = {d\} d z] должен отделять s и t от G\;b — s—t в Gi;j. Тогда каждая из вершин s и t лепестка Q\ смежна только с одной вершиной в G\ , так как лепесток Q x по лемме 1.10 обязан разделять s и t в части G\ . Теперь рассмотрим лепесток Q Так как Q x делит G\;b на две непустые части, одна из частей G jy и G yl пуста (см. вывод 8). Не умаляя общности, будем считать, что это часть G j . В таком случае, вершина t Є Q j смежна не более, чем с двумя вершинами в G \ (это вершины лепестка Q ). При этом в части G\ она смежна лишь с одной вершиной. Таким образом, ее степень меньше четырех. Противоречие.
в четырехсвязном графе
Напомним, что Q x — это лепесток ромашки F : содержащий вершину a . V(F). Предположим, что Q x делит часть G\ на две непустые. Тогда в Giyi нет вершин из множества V(F) \ V(F ) (см. вывод 8). Следовательно, в Gj;i есть вершины из этого множества. Но в Int(G i) есть лишь одна вершина ромашки F — это d\. Тогда d\ V(F ). Если ребра st нет, то по лемме 1.16 получается, что d\ Є V(F ), что невозможно. Значит st Є E(G) (см. рис. 2.37).
Рассмотрим лепесток Qi ромашки F, не пересекающийся с Q\ . Ясно, что он лежит в части G\ , причем одна из частей, на которые он ее делит, пуста (см. вывод 9). Кроме того, Q x П Qi = 0 (см. вывод 2, в качестве Q надо взять Qi, а в качестве Qi — лепесток Q x). Предположим, что пуста именно часть G\p Тогда по лемме 1.11 одна из вершин лепестка Qi смежна с s, а другая — с t. Если какая-то из вершин s и t смежна с обеими вершинами лепестка Qt: то лепесток Q x не разделяет s
Таким образом, если пуста часть G\ то каждая из вершин s и t смежна лишь с одной вершиной из Int(Gi;j). Аналогично, если пуста часть G , то каждая из вершин и и v смежна лишь с одной вершиной из Int(Gi;j). Но при этом одна из этих частей пуста, как мы доказали, а у вершин t и и степень в G \ не больше двух (см. вывод 21). Значит, у какой-то них степень в графе G меньше четырех. Противоречие.
Тогда одна из частей G xj и G lx пуста. Случай 5.1, когда пуста часть G xj, разбирается точно так же, как случай 3.3.2.1, — далее приведен план разбора случая 5.1 с пояснениями некоторых моментов. Кроме того, ниже представлен полный разбор случая 5.2, когда пуста часть G[ х. Стоит отметить, что он во многом повторяет разбор случая 3.3.2.2.
Случай 5.1. Часть G пуста. Вершина v смежна не более, чем с двумя вершинами в части G\ (это вершины лепестка Q x): а вершина t имеет степень не больше двух в Gj;i (см. вывод 21). Тогда t смежна смежна с обеими вершинами лепестка Q x и с вершиной s. Рассмотрим лепесток Qi ромашки F в части G\ , не пересекающийся с Q\ (см. рис. 2.38). Для него справедлив вывод 19 — часть G\ непуста. Но одна из частей G\ и ( пуста, иначе в G\ нет вершин из множества V(F ) \ V(F) (см. вывод 9). Тогда пуста именно часть (.
Вершина и имеет степень 2 в С,ц (см. вывод 21), поэтому и смежна с обеими вершинами лепестка Qi. Отсюда, в F кроме Qi нет лепестков, не пересекающихся с множеством Qij.
Вершина v не смежна ни с кем кроме вершин лепестка Q x в подграфе Gi;j. Аналогичное утверждение верно для той же вершины v и лепестка Qi, не совпадающего с Q x. Тогда лепестки Q x и Qi имеют ровно одну общую вершину, причем v смежна в G\ только с ней. Пусть это вершина d\. По лемме 1.12 в ромашке F есть лепесток {u,di}: а в ромашке F есть лепесток {t,d\}. В ромашке F : кроме Q x: нет лепестков, не пересекающихся с Q\ . Таким образом, все лепестки ромашки F пересекаются с одним из двух лепестков Qi и Qi-i = {u,d\}, а все лепестки F — с одним из двух лепестков Q[ и Q A_I = {t,di}. Тогда по лемме 2.5 ромашки F и F являются малыми, в каждой из них по б лепестков, лепесток ( содержит t: а лепесток Q 2 содержит и.
Вторые вершины лепестков ( и Q 2 совпадают, пусть они оба содержат вершину с -Итак, все лепестки F пересекаются с одним из ее лепестков {s, і] и {u,di}, а все лепестки F — с одним из ее лепестков {s}u} и {t,d\}. При этом у ромашек F и F кроме вершин s, t, и, d\ есть еще две общие — вершины v и б?2- Значит, ромашки F и F — это малые ромашки, и у них ровно по две индивидуальные вершины. То есть выполнен третий вариант нашей теоремы.
Случай 5.2. Часть G lx пуста. Так как вершина и имеет степень 2 в Gj;i (см. вывод 21), она обязана быть смежна с обеими вершинами лепестка Q x. Рассмотрим лепесток Qi ромашки F в части G\ , не пересекающийся с Q\;b (см. рис. 2.39).
Часть Сц не может быть пустой, так как и смежна с обеими вершинами лепестка Q x: который не может совпадать с ( потому что по определению Q x содержит вершину a . V(F). Но одна из частей G\ и ( пуста, иначе в G\ нет вершин из множества V(F ) \ V(F) (см. вывод 9). Тогда пуста именно часть G\ и вершина t смежна не более, чем с двумя вершинами множества Int(Gi;j).
Вершина s не смежна ни с кем из Int(Gi;j), кроме вершин лепестка Q x с одной стороны и кроме вершин лепестка Qi с другой. Совпадать лепестки Qi и Q x не могут, как уже было неоднократно доказано. Следовательно, эти лепестки пересекаются, и их общая вершина является единственной вершиной из Int(Gi;j), смежной с s. Пусть это вершина d\. Из доказанного следует, что, кроме Qi, у F нет лепестков, не пересекающихся с множеством Qij.
Ни один лепесток ромашки F, кроме Qi не содержит -и, потому что в части Gj;i лежит всего один лепесток ромашки F и он содержит s, а в части Giyi вершина и смежна с двумя вершинами лепестка Qi.
Вершина t имеет степень не больше двух в G \ (см. вывод 21). Но при этом часть G\j пуста и состоит из четырех вершин. Следовательно, вершина t смежна с обеими вершинами лепестка Qi. Так как s смежна в Int(Gi;j) только с d\, из леммы 1.12 следует, что множество {t, d{\ является лепестком ромашки F. Аналогично, в F есть лепесток {u,di}.
Предположим, что в F , кроме Q x, есть еще один лепесток Q , не пересекающийся с Q\;b. Одна из частей, на которые он делит часть G\;b) пуста (см. вывод 18). Если это часть, содержащая Q[, то Q совпадает с Q x. Значит, это часть, содержащая Q -. Тогда Q отделяет вершины t и -и от остальных вершин части G\ . Значит, он обязан содержать все вершины внутренности этой части, смежные с t. То есть этот лепесток должен содержать (. Следовательно, Q = Qi. Но часть ( непуста, так как вершина а Є Q x содержится в этой части и по определению не лежит в V(F). Отсюда по лемме 1.9 графы ( — Qi — и и ( — Qi — v связны. Значит, лепесток Qi не разделяет и nv в G\ — E(Q 1, Q j), что невозможно по лемме 1.10.
Итак, в F : кроме Q x: нет лепестков, не пересекающихся с множеством Qij. Теперь докажем, что в F не может быть лепестка, содержащего v и отличного от Q j. В части С-1 таких лепестков нет, потому что все лепестки в этой части содержат одну из вершин s и t по лемме 2.7. А в части G вершина t смежна с обеими вершинами лепестка Qi. Таким образом, почти все лепестки ромашек F и F определены. Неясно пока только, есть ли в F лепесток, отличный от Qi и содержащий и: и есть ли в F лепесток, отличный от Q j и содержащий t: и если они есть, то в каких частях эти лепестки лежат.
Докажем, что либо они оба есть, либо обоих нет, и если эти лепестки есть, то они пересекаются и либо они оба лежат в G\ , либо оба — в G \. Действительно, если какой-то из описанных лепестков есть, то по лемме 2.9 вторая его вершина является единственной, смежной с -и в соответствующей части. А тогда по лемме 1.16 эта вершина содержится в множестве вершин обеих ромашек, то есть является второй вершиной обоих описанных лепестков.
Значит, либо обе ромашки F и F — это ромашки VKlnna (если дополнительных лепестков нет), либо обе — И- -типа (если эти лепестки есть), и в любом случае у них ровно по две индивидуальные вершины (вершины а и Ъ лежат в V(F ) \ V(F)). То есть выполнен либо четвёртый, либо пятый вариант нашей теоремы.
