Содержание к диссертации
Введение
Глава 1. Теорема Хелли для клик .
Глава 2. Независимые трансверсали .
Глава 3. Хроматические числа слоистых графов с ограниченной степенью вершин .
Глава 4. Хроматические числа слоистых графов с ограниченной максимальной кликой .
Глава 5. Метод одновременной перекраски .
Список литературы
- Теорема Хелли для клик
- Независимые трансверсали
- Хроматические числа слоистых графов с ограниченной степенью вершин
- Хроматические числа слоистых графов с ограниченной максимальной кликой
Введение к работе
Одним из важнейших и сложнейших направлений исследований в теории графов является изучение хроматических чисел различных графов. Хроматическим числом графа называется наименьшее натуральное число п такое, что граф допускает правильную окраску в п цветов, но не допускает правильную окраску в меньшее количество цветов. Правильной называется такая окраска вершин графа, при которой смежные вершины имеют различные цвета. Одним из наиболее классических результатов в этой области является теорема Брукса, утверждающая, что хроматическое число графа степени п, максимальная клика которого имеет мощность /, равно п. Это утверждение перестает быть верным, если степень графа увеличить до п + 2. Bruce Reed в 1998 году доказал, что для достаточно больших п степень графа в формулировке теоремы Брукса можно увеличить до п + 1(См. [18).
Также было получено множество результатов, связывающих степень графа и его хроматическое число с размером максимальной клики. В частности, хотелось бы отметить статью [31], в которой доказано, что существует раскраска графа G степени п с co(G) п + 1 в п цветов, в которой максимальная антиклика монохроматична и результат А. В. Косточки [22] установившего, что если d(G) — u(G) mm{0(rd(G) 4), 0(г2)}, то X{G) d(G) - r.
Многие исследования были посвящены обобщению теоремы Брукса для различных классов графов, например в статье [34] теорема обобщена на случай графа, не содержащего данного дерева на п + 2 вершинах: доказано, что в этом случае степень графа тоже может быть увеличена до п + 2 для любого п, при этом размер максимальной клики и хроматическое число тоже будут равны п. Также немало усилий было приложено к поиску алгоритмов нахождения правильной окраски графов, например алгоритм Grotschel, Lovasz и Schrijver для окраски совершенного графа за полиномиальное время или алгоритм Карлоффа [35] окраски графа степени п без Кп+\. Особое место занимает исследование сильного хроматического числа графа, связанного с его разбиением на равномощные множества, вершины которых затем окрашиваются в различные цвета. Оценки, связывающие такие хроматические числа со степенью графа были получены в 2] и развиты в [3], по сути эти исследования сводятся к получению оценок на хроматические числа слоистых графов, г. е. графов, разбивающихся на равномощные клики. В дальнейшем, в статье [6] была получена точная оценка на степень слоистого графа, допускающего правильную окраску в количество цветов, равное размеру максимальной антиклики, но только для случая не более, чем трех слоев.
Еще одним популярным направлением исследований являются исследования графов клик, в частности, графов с условием Хелли на клики (Clique-Helly graphs). Обзор результатов по этой тематике можно найти в [13]. В статье [14J было получено описание некоторого вида графов, которые могут быть графами клик для других графов. Оказалось, что таковыми являются именно те графы, которые обладают свойством Хелли для клик. В дальнейшем этот результат был обобщен в статье [15].
Теорема Хелли для клик
Графы клик изучаются уже давно и многие результаты стали классическими. Важное место в этой теории занимают графы с условием Хелли на клики (Clique-Helly graphs), т. е. графы, в которых любой набор попарно пересекающихся максимальных (по количеству вершин) клик имеет общую для всех этих клик вершину. Ряд результатов на эту тему изложен в работе 13.
В этой главе будет рассмотрена связь между степенью графа и размером максимальной клики и будет выведено простое соотношение, позволяющее определить значительный класс графов с условием Хелли на клики (см. георему 1 и следствие 3).
Лемма 1. х Пусть число вершин в графе G не превосходит 2п—1; а после удаления любой вершины найдется клика мощности п. Тогда в графе G есть клика мощности п + 1. Доказательство. Предположим противное. Рассмотрим минимальное п, для которого не выполняется утверждение леммы и граф G — контрпример для п. Пусть в этом графе 2п — t вершин. Пусть Н — дополнение графа G. Все дальнейшие рассуждения будут проводиться с графом Н. Рассмотрим любую антиклику этого графа, содержащую и вершин (т. е. n-клику в G). Множество ее вершин обозначим через А", а множество остальных вершин — через Y. Назовем подмножество М С Y плохим, если оно либо пусто, либо количество вершин в М больше количества вершин в X, смежных хотя бы с одной вершиной из М. Обозначим через А максимальное плохое подмножество Y (оно может быть и пустым), а через В —множество вершин из X, смежных с вершинами из Л. Пусть А = к. Тогда двудольный граф с долями Y\A и X \ В и ребрами графа Н между этими долями будет удовлетворять условию теоремы Холла (см. [6j) (иначе А — не будет максимальным плохим подмножеством), поэтому каждой вершине Y\A можно поставить в соответствие смежную с ней вершину X \ В таким образом, чтобы все эти смежные вершины были различны. Множество несопоетавленных вершин X обозначим через В. Ясно, что В содержит ровно к + t вершин. Рассмотрим граф Н , образованный вершинами AUB и ребрами графа Н, соединяющими эти вершины. Заметим, что при удалении любой вершины из Н в графе Н должна была найтись антиклика с п вершинами, но в нее могло входить не более, чем n — k — t вершин из (X U Y) \ (A\JВ), так как вершины этого множества разбиты ровно на п — к — t пар смежных. Следовательно, остальные k + t вершин должны быть из Ли В. Поэтому в Н после удаления любой вершины найдется антиклика с k + t вершинами. Тогда либо либо A = Y, либо в Н найдется антиклика с к+t+l вершинами в силу минимальности п, поскольку \Н \ = 2к + t 2(к + t) — 1. Во втором случае заметим, что при добавлении к вершинам этой антиклики всех вершин из X \ В получим антиклику сп + 1 вершинами. В первом случае в графе G найдется вершина, смежная со всеми остальными (это любая вершина из X \ В ). Отбросим ее, тогда по условию найдется клика с п вершинами. Добавляя к ним отброшенную, получим клику сп+1 вершинами. Полученное противоречие доказывает утверждение леммы.
Лемма 2. Если в некотором графе G максимальная клика имеет мощность п и при этом найдется набор попарно пересекающихся п-клик, не имеющих общей вершины, то в этом, графе не менее 2п вершин.
Доказательство. Предположим, что утверждение леммы не выполняется. Тогда в графе G будет не более 2п — 1 вершин. Следовательно, для него выполняется условие леммы 1. Тогда можно удалить какую-то вершину графа G таким образом, что размер максимальной клики будет не более п — 1. Но это означает, что все его п—клики будут иметь общую вершину.
Независимые трансверсали
Нахождение верхних оценок на хроматические числа графов с ограниченными размерами максимальной клики и степени является классической задачей. Наиболее яркий результат — теорема Брукса, утверждающая, что в графе степени п 3, не содержащем клик на п + 1 вершинах, хроматическое число не превосходит п (см. [17J). Позднее Брюсом Ридом было получено усиление этого результата: для достаточно большого п в графе степени п + 1, не содержащем клик на п + 1 вершинах, хроматическое число не превосходит п (см. [18]). Напрямую дальнейшее усиление невозможно, что показывает пример клики на п + 3 вершинах, из которой удалены все ребра антицикла на пяти вершинах. В этом графе максимальная клика имеет мощность п, степень равна п + 2 а хроматическое число равно п + 1. Для нахождения дальнейших связей между степенью графа, его хроматическим числом и размером максимально!) клики оказывается важным нахождение максимальной анитклики, пересекающей все максимальные клики независимой трансверсали всех максимальных по размеру клик. В этой главе будут рассмотрены вопросы, связанные с независимыми трансверсалями, пересекающими все п—клики графа G . Основным результатом этой главы будет доказательство того, что в графе не очень большой степени (не более, чем в полтора раза большей мощности максимальной клики) существует независимая трансверсаль. Также будет доказана точность полученной оценки. Сначала рассмотрим структуру графа ?-клик для графа G, в котором u(G) = п и do п + к, где п 2(к + 1). Лемма 4. Пусть граф G такой, что ou(G) — п, d(G) n + к, где к [п] — 1, и пересечение любых двух п-клик непусто. Тогда n(T(G)\L(G)) 2(n-\n(L(G))\).
Доказательство. В силу теоремы 1, \n(L(G))\ 0. Тогда \n(T(G))\ п + k + 1, поскольку любая вершина из L(G) смежна с любой вершиной из T(G). Ясно, что любая п-клика, содержащая L(G), имеет п— \n(L(G))\ вершин в T(G) \ L(G) (если \n(L(G))\ = п, то утверждение леммы очевидно). Заметим, что при удалении любой вершины из T(G) \ L(G) найдется п-клика, содержащая L(G), но не содержащая выкинутой вершины (иначе эта вершина но определению входила бы в L(G)). Но в T(G) \ L{G) нет клик, содержащих более п — \n(L(G))\ вершин (иначе объединение такой клики с L{G) будет кликой G, содержащей более п вершин). Если любые две n—n(L(G))-KjniKH из T(G)\L(G) пересекаются, то в силу леммы 2, граф T{G) \ L(G) содержит не менее 2(n — n(L(G ))) вершин. Если же какие-то две п— ?г(Ь(С))-клики из T(G)\L(G) не имеют общих вершин, то в их объединении содержится уже 2(п — \n(L(G))\) вершин, принадлежащих T(G) \ L(G).
Рассмотрим граф гг-клик для графа G относительно пересечения. Определим структуру этого графа п-клик для графа G, в котором CJ(G) = п и d(G) п + к, где п 2{к, + 1). Определение 1. Назовем ядром некоторой клики пересечение всех п-клик, пересекающихся с данной- кликой. В частности, если данную п-клику не пересекает ни одна другая г-клика, то ядро будет совпадать с самой кликой. Лемма 5. Пусть G — такой граф, что UJ(G) = п, d(G) п + к, и п 2(fc+ 1). Тогда все ядра будут содержать не менее п — к — 1 вершин. Доказательство. Поскольку d(G) г + к, то в силу следствия 1, любой набор попарно пересекающихся n-клик имеет не менее п — к — 1 общих вершин. Поскольку п 2(к + 1), то это составит более половины мощности всей п-клики. Следовательно, любая клика, пересекающаяся с какой-нибудь из клик набора, также содержит какую-нибудь из этих п — к — 1 вершин. Тогда любые две //-клики, пересекающиеся с данной, пересекаются между собой. Тогда, в силу следствия 1, все эти клики имеют не менее и — к — 1 общих вершин, откуда, в частности следует, что все ядра содержат не менее, чем п — к — 1 вершин. Заметим, что так как 2(п—к— 1) //, то каждое ядро содержит более половины вершин клики. Следовательно, любые две пересекающиеся клики имеют общее ядро. Таким образом, граф /г-клик для рассматриваемого графа выглядит как объединение нескольких компонент, каждая из которых является кликой. Все гг-клпки, соответствующие каждой компоненте, имеют общее ядро. Поэтому чтобы найти независимую трансверсаль, пересекающую все n-клики, достаточно найти независимую трансверсаль, пересекающую все ядра. Определение 2. Для вершины а ядра внешней степенью этой вершины будем называть количество вершин графа G, смежных с а и не входящих в объединение /г-клик, содержащих а. Ребра, соединяющие вершину а с вершинами, не входящими с а в одну гг-клику, будем называть внешними. Лемма 6. Пусть G - такой граф, что oo(G) = п, d(G) п + к, и п 2(/ + 1). Рассмотрим ядро J, содержащее n — t вершин. Тогда внешняя степень любой вершины этого ядра будет не более к — t + 1. Доказательство. В силу леммы 4, объединение клик, содержащих ядро ,7, имеет не менее 2(/? — (n — t)) + (?г — t) = n + t вершин. Так как вершины J будут смежны со всеми вершинами, входящими в объединение клик, содержащих «7, то из общего количества исходящих ребер для данной вершины из J, не превосходящего п + к, не менее, чем п + t — і будет соединять эту вершину с вершинами из объединения клик, т. е. не будут внешними. Следовательно, внешними могут быть только оставшиеся не более, чем к — t + 1 ребер. Сформулируем и докажем теорему, которая является основным результатом этой части статьи. Теорема 3. Пусть G такой граф, что UJ{G) = п, d(G) n + k, и п 2(к + 1). Тогда существует независимое подмножество М zV такое, что при удалении из G всех вершин множества М кликовое число графа уменьшится. Доказательство. 1. Сначала определим множества М и iVi а также класс эквивалентности Т\. Пусть М такое множество, что \J П М\ = 1 для любого ядра J и \E(G(M))\ — минимально (такие множества будем называть отмеченными). Вершину х . М, содержащуюся в каком-то ядре J и не смежную ни с одной вершиной из М, кроме вершины того же ядра, будем называть свободной. Множество всех свободных вершин назовем S(M) (это множество зависит от М). Если в J есть свободная вершина х Є J, то для вершины t Є J П M (ясно, что такая вершина t существует и единственна), множество M = MU{x}\ {} (1) будет отмеченным и С(М ) = С(М) в силу минимальности. Будем такие операции называть операцией 1. Рассмотрим класс Т\ таких множеств М относительно серии всех возможных последовательных операций 1. Поскольку операции 1 обратимы, то Ті будет классом эквивалентности.
Хроматические числа слоистых графов с ограниченной степенью вершин
В этой главе будет доказана оценка на хроматическое число графа, называемого слоистым, представимого в виде объединения непересекающихся n-клик, называемых слоями. Эта задача была поставлена Н. Алоном в 1992 году в [2]. В этой статье была получена некоторая оценка на степень такого графа, при которой он допускает правильную раскраску в п цветов. В 2004 году она была существенно улучшена в статье Хакселла [3]. В дальнейшем, в сіатье [6] была получена точная оценка на степень тг-слоистого графа, допускающего правильную окраску в п цветов, но только для случая не более, чем трех слоев. В настоящей статье будет получено общее неравенство, из которого буде і следовать, в частности, общая оценка Хакселла.
Для небольших значении п получен результат, улучшающий эти оценки в некоторых специальных случаях. Определение 3. Граф будем называть п-слоистым, если его вершины можно разбить на непересекающиеся г-клики (такие клики будем называть слоями). Для таких графов выполняется следующая теорема, связывающая максимальную внешнюю степень вершин /г-слоистых графов с числом слоев при условии, что хроматическое число графа, также равно п. Теорема 4. Пусть G такой п-слоистый граф, что V(G) = nq, d(G) n + k, причем (3(k +1)- n)q 2k + 4. Тогда \(G) = n. Доказательство. Аналогично доказательству основной теоремы предыдущей части, доказательство будет основано на построении процесса, при котором множество вершин одного из цветов, остающихся неподвижными при этом процессе, будет неограниченно расти, что придет в противоречие с исходной посылкой о том, что искомой раскраски не существует. 1. Сначала определим множества М и JVi а также класс эквивалентности Т\. Рассмотрим какую-нибудь раскраску вершин G в п цветов, при которой минимально количество ребер, соединяющих одноцветные вершины (такие ребра будем называть плохими) и при этом вершины каждого цвета лежат в разных слоях но одной. Обозначим через А{ множество всех вершин цвета г 1, а через М — множество всех вершин цвета 1. Предположим, что существует ребро, соединяющее две вершины из М. Вершину х цвета г, отличного от 1, будем называть свободной, если она не соединена внешними ребрами с вершинами цвета 1 и вершина у цвета 1, лежащая в ее слое, не соединена внешними ребрами с вершинами цвета і. Множество всех свободных вершин назовем S(M). Отметим, что множество S(M) зависит от раскраски. Заметим, что если поменять цвета вершин х и у (назовем эту операцию обменом), то количество плохих ребер не увеличится. Рассмотрим класс эквивалентности Ті таких множеств М относительно серии всех возможных последовательных операций обмена со свободными вершинами всевозможных цветов ", отличных от цвета 1. Рассмотрим множество вершин JV"i, которые принадлежат пересечению всех множеств, входящих в Ту. Нашей целью будет доказательство того, что N\ = 0. 2. Опишем первый шаг процесса. Предположим противное. Пусть 7Vi = s. Ясно, что s 2, поскольку в N\ входят две вершины, изначально соединенные ребром (иначе операцией обмена с одной из этих вершин можно было бы уменьшить количество плохих ребер). Заметим, что с вершинами из N\ внешними ребрами соединено не более s(k + 1)-2 вершин из слоев, содержащих вершины из N\. Следовательно, найдется такой слой W\, в котором этих вершин не более к+1. Вершина этого слоя t\, входящая в N\, будет смежна не более, чем с к + 1 вершинами других слоев. Поскольку из условия следует, что 2к + 2 п — 1, то в W найдется вершина а\ t\, не соединенная внешними ребрами с вершинами из N\ и не совпадающая по цвету с вершинами других слоев, смежных с t\. Свойства вершины а\ сохраняются при операциях обмена, поскольку эти операции производятся только со свободными вершинами, а вершина t\ всегда будет цвета 1, следовательно вершины, соединенные с ней внешними ребрами, никогда не будут свободными. Кроме того, вершина а\ ни в какой момент не была свободной, так как t\ Є iVi- Выберем множество М\ Є Т\ таким образом, чтобы количество вершин из Мі, смежных с a i и не входящих в один слой с ai (множество таких вершин обозначим через Pi), было минимальным по всем множествам из Ті.-Отметим, что множество Рі не может быть пустым, поскольку иначе вершина ах была бы свободной. Рассмотрим множество Z\ всех таких вершин и Є Pi \ Mi, что и не входит в слой, содержащий ai.
Правая часть этого неравенства положительна в силу того, что \Nq\ 7 " по условию (3(к + 1) - n)q 2к + А. Но поскольку число \N(\ монотонно возрастает, то этот процесс должен когда-нибудь закончиться. Получилось противоречие с тем, что N\ непусто. Но если Л пусто, то никакие вершины из М не смежны, иначе операция обмена, проведенная с одной из таких вершин уменьшит количество плохих ребер, что противоречит выбору исходной раскраски. Аналогично, никакие вершины каждого из остальных цветов несмежны, поэтому исходная раскраска — правильная. Следствие 5. Пусть G — некоторый такой граф, вершины которого можно разбить на непересекающиеся не более, чем п—элементные множества Л\, Л 2,... А8 таким образом, что внешние степени всех вершин не превосходят . Тогда этот граф п—хроматичен.
Хроматические числа слоистых графов с ограниченной максимальной кликой
Рассмотрим следующую задачу, которая была поставлена в статье [1]: пусть граф G является n-слоистым с максимальной кликой мощности п и состоит из к слоев. Какое максимальное хроматическое число он может иметь? Для четных к верна следующая оценка: Лемма 9. Пусть в п-слоистом графе G будет 2кп вершин, причем максимальная клика имеет мощность п. Тогда максимальное хроматическое число такого графа не более кп.
Доказательство. Заметим, что для достаточно больших п существуют графы на п вершинах без треугольников с маленькой антикликой (см. [8). Более того, в статье 9j было доказано, что Лд г т- Откуда несложно вывести, что для всех п 2 существует граф с п вершинами без треугольников, максимальная антиклика которого содержит менее In Пу/п вершин.
Через a(G) будем обозначать максимальную антиклику графа G, содержащего п вершин. Выберем такое маленькое с О, что для любого графа G без треугольников с п вершинами, в котором ——- е, найдется граф G\ без треугольников с п вершинами и a(Gi) 1ппл/п и, кроме того, п 10А;3. (Ясно, что при достаточно маленьких є число вершин G должно быть велико). Для этого є найдем граф G с наименьшим количеством вершин такой, что a,L" е. Теперь обозначим через п количество вершин графа G. Тогда =. Выберем в графе G максимальную антиклику а\, удалим ее, затем в получившемся графе снова выберем максимальную антиклику а2, удалим ее и так до а&. Заметим, что поскольку каждая из этих антиклик содержит менее 4= вершин, то в объединении они содержат менее k) j= пМЫп вершин, что меньше //,, поэтому все ai будут непусты.
Рассмотрим граф H. Добавим к каждому из множеств щ а і — щ вершин. Соединим добавленные вершины со всеми остальными вершинами кроме тех, которые лежат с ними в одной образовавшейся антиклике мощности а,\. Множество добавленных вершин обозначим через М, а число ai обозначим через л. Докажем, что граф, дополнительный к получившемуся, будет искомым графом G . Действительно, во-первых, получившийся граф G будет п-слоистым. Во-вторых, максимальная клика графа G \ М будет мощности п, поскольку максимальная антиклика графа G имела мощность п. Пусть какая-то клика графа G содержит вершину А из М. Тогда она может содержать только вершины слоя, содержащего А, поскольку А не смежна с остальными вершинами. В-третьих, в графе G \ М нет антитреугольников, поэтому его хроматическое число не менее — —-. Оценим это число. Поскольку в силу неравенства 3 ai — а; = ai — а& (к — 1)аіЦ=, то \М\ (к— 1)2\а\ р (к— 1)21п2п, откуда и получается требуемое неравенство.
Полученная оценка снизу для четных к при больших п очень близка к верхней оценке. В случае нечетного к ситуация сложнее. Сначала приведем методику получения оценки в общем случае. Для этого сделаем несколько предварительных замечаний.
Пронумеруем слои графа G числами от 1 до А;. Рассмотрим граф G , дополнительный к G. Любые два слоя содержат полное паросочетание в силу леммы Холла. Рассмотрим ребра этих паросочетаний, соединяющие слои с соседними номерами, а также слой с номером к и слой с номером 1. Они образуют граф, степени всех вершин которого равны 2. Этот граф разбивается на циклы. Заметим, что длина каждого из циклов делится на к, поскольку слои будут чередоваться при движении по ребрам цикла. Отметим, что это дает нам простую оценку на хроматическое число графа G. Действительно, каждый цикл после удаления одной из вершин можно разбить на пары смежных вершин, поэтому граф G разбивается на пары смежных вершин после удаления из него не более п вершин, поэтому его можно разбить не более, чем на т ( + п — n клик, откуда хроматическое число G не превосходит Ц—- (эту оценку можно получить и просто удалением одного из слоев). Но эту оценку можно значительно улучшить если заметить, что циклы можно "склеивать", т. е. в случае, когда два цикла соединены ребром, то их объединение можно полностью разбить на пары. Кроме того, есть еще ряд ситуаций, когда можно придумать более удачное разбиение графа G на клики.
Рассмотрим паросочетание Р максимальной мощности в графе G такое, чтобы в него вошли вершины нескольких полных циклов. Очевидно, что останется несколько нечетных циклов. Будем называть эти циклы базовыми. Индуцированный подграф G , образованный вершинами базовых циклов, обозначим через Z. Заметим, что никакие две вершины двух различных базовых циклов несмежны, поскольку иначе можно было бы разбить объединение этих циклов на пары смежных вершин, что противоречит максимальности выбранного паросочетания. Окрасим ребра выбранного паросочетания в цвет 1, а все остальные ребра графа G , кроме ребер, входящих в Z в цвет 2. Простои путь будем называть чередующимся, если цвета ребер в этом пути чередуются и он не проходит через ребра Z (для простоты введем соглашение, что в чередующемся пути могут совпадать первая и последняя вершины).
Доказательство. Пусть два базовых цикла С\ и Сч соединяются чередующимся путем. Тогда рассмотрим вершины этих циклов, принадлежащие этому пути. Заметим, что после удаления этих вершин циклы С\ и Сг можно будет разбить на пары смежных вершин. Кроме того, вершины чередующегося пути тоже разбиваются на пары, соединенные ребрами цвета 2. Но тогда полученные пары можно добавить к исходному паре-сочетанию, что противоречит его максимальности.
Рассмотрим любой базовый цикл С\. Назовем полуорбитой этого цикла индуцированный подграф G , образованный объединением вершин всех чередующихся путей, которые начинаются и заканчиваются в С\ (при этом можно допустить совпадение первой и последней вершин этих путей) и вершин самого цикла С\. Поскольку чередующийся путь не может проходить через вершины базовых циклов, то каждая вершина из Z может принадлежать ровно одной полуорбите. На самом деле верны более общие утверждения: Лемма 12. Никакие две полуорбиты не пересекаются.
Доказательство. Предположим, что найдется вершина А, принадлежащая одновременно полуорбитам 0\ и Оч, образованных циклами С\ и Сг соответственно. Рассмотрим какой-то чередующийся путь Pi, начинающийся и кончающийся в С\ и проходящий через А. Будем двигаться по этому пути от какой-то вершины X Є С\ к вершине Y Є С\ (возможно, X = Y). Рассмотрим на этом пути самую первую вершину, принадлежащую полуорбите Ог- Обозначим эту вершину через В. Тогда найдется чередующийся путь Р2, начинающийся и кончающийся в С2, проходящий через В. Тогда рассмотрим путь, который сначала идет от X к В по чередующемуся пути Pi, затем идет по чередующемуся пути Р2 в С2, причем в ту сторону, чтобы ребро этого куска пути Р2 отличалось по цвету от ребра, по которому мы пришли в В но пути Pi.
Доказательство. Предположим, утверждение леммы не выполняется. Рассмотрим тогда самый короткий чередующийся путь Р, соединяющий некоторую полуорбиту 0\, образованной циклом Сі с полуорбитой 02, образованной циклом С2. Пусть этот путь соединяет вершину А Є 0\ с вершиной В Є 02. Тогда рассмотрим чередующиеся пути Pi начинающийся и кончающийся в Сі и проходящий через А, и Р2 начинающийся и кончающийся вС2и проходящий через В. Обозначим через Pi и R2 куски путей Pi и Р2: которые соединяют вершины А и В с циклами Сі и С2 соответственно и при этом ребра Pi и R2, выходящие из вершин А и В отличались бы по цвету от ребер пути Р, выходящих из вершин А а В соответственно. Тогда путь P1UPUP2 будет чередующимся путем, соединяющим циклы Сі и С2, что противоречит утверждению леммы 11.
