Содержание к диссертации
Введение
Глава 1. Предварительные результаты 16
Глава 2. Графы, содержащие 4-коклику 32
Глава 3. Графы, не натягиваемые на некоторую 3-коклику 35
Глава 4. Графы, разбиваемые на три клики 41
Глава 5. Графы, натягиваемые на любую 3-коклику 47
Список литературы 91
- Графы, содержащие 4-коклику
- Графы, не натягиваемые на некоторую 3-коклику
- Графы, разбиваемые на три клики
- Графы, натягиваемые на любую 3-коклику
Введение к работе
ПОСТАНОВКА ЗАДАЧИ. В настоящей работе исследуется класс графов без 3—лап и сопутствующие частичные геометрии. Имеется несколько источников интереса к исследованию предпринятому в настоящей работе. И как это часто бывает, приведенные ниже точки зрения имеют тесные внутренние взаимосвязи.
Первый источник лежит в области общей теории графов. Здесь и далее под словом граф мы понимаем конечный неориентированный граф без петель и кратных ребер. Если Г — граф, то посредством У (Г) и Е(Г) обозначим, соответственно, множество вершин и множество ребер графа Г. 6-лапой называется полный двудольный граф с долями из одной и трех вершин. Далее всюду, если не оговорено противное, подграф из Г будет означать порожденный подграф графа Г, то есть подграф, в котором вершины смежны тогда и только тогда, когда они смежны в Г. О графе мы говорим, что он является графом без 3-лап, если он не содержит подграфов изоморфных 3-лапе. Класс графов без 3-лап содержит такой важный класс графов, как реберные графы. Реберным графом мы называем любой граф Г, который изоморфен графу (Д), для подходящего графа А, где (Д) — граф вершинами, которого являются ребра графа А, причем две вершины смежны тогда и только тогда, когда их пересечение одноэлементно.
Класс графов без 3-лап можно рассматривать как класс, являющийся наиболее интересным расширением класса реберных графов, при этом он гораздо шире, и вместе с тем графы этого класса наследуют многие свойства реберных графов. Треугольник Т (полный подграф на трех вершинах) графа Г называется нечетным, если в Г \ Т существует вершина смежная Г в точности с нечетным числом вершин. В [10] доказано, что следующие условия эквивалентны:
(1) Г — реберный граф;
(2) Г не содержит 6—лап, и если два нечетных треугольника имеют общее ребро, то подграф, порожденный их вершинами, является полным подграфом.
Из ее формулировки видно, почему в качестве расширения класса реберных графов был выбран класс графов без 3-лап.
До последнего времени задача изучения графов без 3-лап при доста точно общих дополнительных ограничениях казалась сложной. Условие отсутствия 3-лап относится к, так называемым, локальным свойствам. Говорят, что граф обладает локально свойством Р, если подграф порожденный вершинами окрестности произвольной вершины этого графа об-ладет свойством Р. Если а — вершина графа Г, то через [а] будем обозначать окрестность вершины а, то есть множество вершин графа Г, смежных с а, а через а1 — объединение [a] U {а}, которое назовем замкнутой окрестностью вершины а. п—кликой (соотв. кокликой) графа Г называется любое его п—подмножество любые две вершины которого смежны (соотв. несмежны) в Г. Таким образом, графы без 3-лап — это в точности графы, в которых окрестность всякой вершины не содержит 3-коклик. Можно сказать, что задача полного описания графов без 3-лап является задачей восстановления графа по информации о его локальной структуре. Эта задача в такой постановке в основном изучается для точечных графов конечных геометрий (см. [13]) и других комбинаторно-симметричных графов.
Сложность задачи восстановления графа по его локальным свойствам, в первую очередь связана с тем, что имея даже хорошее представление
0 строении окрестности каждой вершины графа в общем случае невозможно получить информацию о строении графа порожденного объединением окрестностей двух вершин графа, находящихся на расстоянии и 2 в графе. Поэтому на этапе изучения необходимы дополнительные предположения о "взаимодействии"окрестностей вершин. Пусть а и 6 — вершины графа Г. Тогда подграф, порожденный пересечением [а] П [6] их окрестностей называется Л—подграфом, если они смежны, и /І—подграфом, если они находятся на расстоянии 2. Последний из них обозначается М(а,Ь). Именно строение //—подграфа М(а,Ь) позволяет связать свойства окрестностей вершины а и Ъ. Скажем, что Г — граф с некликовыми //—подграфами, если любой его //—подграф содержит пару несмежных вершин. Вместе с тем, как нетрудно видеть, любой граф не содержащий 3-коклик является графом без 3-лап, поэтому для того, чтобы условие отсутствия 3-лап не было вырожденным необходимо потребовать, чтобы каждая связная компонента содержала 3-коклику. При этом, как нетрудно видеть, выполнение условия отсутствия 3-лап и некликово-сти //—подграфов для всего графа эквивалентно выполнению этих условий для всех его связных компонент. Итак, мы приходим к задаче изучения связных графов без 3-лап с некликовыми //—подграфами, содержа щих 3-ко клику.
С другой стороны, класс графов без 3-лап с некликовыми р— подграфами, содержащих 3-коклику, содержит некоторые важные семейства комбинаторно симметричных графов. Такими семействами, например, являются реберные графы полных и полных двудольных графов, соответственно, треугольные и решетчатые графы. Если Кп и Кт п — полный граф с п вершинами и полный двудольный граф с долями из тип вершин, то Т(п) = (Кп) — треугольный граф, а (Кт,п) — т х п—решетка. Треугольные графы и квадратные решетки (cm — п), в частности, обладают свойством сильно-регулярности. Граф Г называется сильно-регулярным, если он имеет диаметр 2, и существуют такие числа к, А, р, что мощность окрестности любой вершины равна к, число вершин в любом Л—подграфе равно Л, а число вершин в любом //—подграфе равно р. Если v — число вершин графа Г, то говорят, что Г — сильнорегулярный граф с параметрами (и, &, Л, р).
Графы без 3-лап с несвязными /х-подграфами были изучены А. Брауэ-ром и М. Нуматой [8]. Они получили полное описание всех таких графов, причем не только с конечным числом вершин. В частности, они показали, что если граф связный конечный и содержит 3-коклику, то он является т х п-решеткой. Последний результат был обобщен В. Кабановым в [1]. Им было доказано, что связный редуцированный граф без 3-лап содержит 3-коклику, а любой его //-подграф имеет радиус больше 1, тогда и только тогда, когда он является либо треугольным графом Т(п) с п 6, либо 7тг х п-решеткой сп 3ига 3, либо графом Шлефли. Граф Шлефли — это единственный сильно-регулярный граф с параметрами (27,16,10,8).
Результаты настоящей работы обобщают результаты А. Брауэра, М. Нуматы и В.В. Кабанова.
Перейдем теперь к источнику связанному с конечными геометриями. Система инцидентности S = (Р, В, I) с множеством точек Р, множеством блоков В и симметричным отношением инцидентности / с тем свойством, что / С (Р х В) U (В х Р) называется геометрией ранга 2. Двойственная к S геометрия SD = (PD, BD, ID) получается, если положить PD = В, BD = Р и I = І. В случае, когда В не содержит блоков инцидентных одним и тем же точкам из Р (неразличимых блоков), каждый элемент JB можно отождествить с подходящим подмножеством из Р. Если такое отождествление имеется, то пишут S = (Р,В). Две точки называ ются коллинеарными, если обе они лежат в некотором блоке из В. Точечным графом называется граф с множеством вершин Р и отношением смежности, полученным удалением из отношения коллинеарности диагонали квадрата Р2. Точечный граф геометрии S обозначим TS. Иногда по точечному графу можно однозначно восстановить геометрию.
Для точки х положим х1 = {у є Р\х у}, где — отношение коллинеарности. Вычетом геометрии S в точке х называется геометрия S = (РХ,ВХ,1Х), где Рх = х±\ {х}, Вх = {Цх Є L,L Є В} и І = ІГ\ ((Рх х Вх) U (Вх х Рх)). Теперь мы можем сказать, что в случае, когда точечный граф определяет геометрию, задача восстановления этого графа по окресностям вершин эквивалентна восстановлению геометрии по ее вычетам. Задача восстановления графа по окрестностям вершин является сложной даже тогда, когда действие его группы автоморфизмов транзитивно на множестве вершин. Ситуация становится сложнее, если нам известно лишь то, что подграфы, порожденные окрестностями вершин попарно изоморфны (комбинаторный аналог вершинной транзитивности группы автоморфизмов графа). Однако в некоторых случаях приходится рассматривать графы, у которых подграф порожденный окрестностью произвольной вершины принадлежит некоторому классу графов Т. Тогда наличие единого структурного описания этого класса может быть полезным. Например, структурное описание класса графов без 3-лап с равномощными ц—подграфами было полученно в работе [3]. Затем это описание было использовано в работах [2], [4], [5], [6] для харак-теризации графов Грассмана и Джонсона.
Наконец, еще один взгляд на изучаемую проблему дает теория конечных частичных геометрий. Частичное линейное пространство — это такая конечная геометрия ранга 2, в которой нет неразличимых блоков, а любые две точки принадлежат не более чем одному блоку, при этом каждый блок содержит по крайней мере две точки. В теории частичных линейных пространств вместо Р принято писать X, а вместо В — С. При этом элементы С называют прямыми. Обобщенным четырехугольником называется частичное линейное пространство, такое, что если точка х не лежит на прямой /, тогда х коллинеарна единственной точке прямой /. Обобщенный четырехугольник называется вырожденным, если некоторая точка коллинеарна всем остальным точкам. В вырожденном обобщенном четырехугольнике множество прямых образует пучок. Обобщенный четырехугольник определяется своим точечным графом, причем пря мым соответствуют максимальные клики. Размер прямых обобщенного четырехугольника одинаков, за исключением случая, когда точечный граф изоморфен неквадратной решетке. Нетривиальные обобщенные четырехугольники с прямыми размера 3 описаны. Графы дополнительные к их точечным графам — это в точности 3 х 3—решетка, граф Т(6) и граф Шлефли (см. [9]). Все эти графы не содержат 3-лап и, как мы увидим, это не случайно. Геометрия, дополнительный граф к точечному графу которой изоморфен графу Шлефли, обозначается GQ(2,4).
Антифлагом называется пара (х, L), состоящая из точки и прямой, ее не содержащей. Положим а(х, L) — число точек инцидентных L и колли-неарных х. Пусть р — натуральное число, частичное линейное пространство называется —однородным, если а(х, L) равно 0 или (р для любого антифлага, и сторого —однородным, если а тождественно равно р. Фактически описание обобщенных четырехугольников с прямыми размера 3 — это описание строго 1-однородных частичных линейных пространств с прямыми размера 3. Вопрос описания 1 -однородных частичных линейных пространств с прямыми размера два и три открыт. Такие геометрии также однозначно определяются своими точечными графами.
Пусть S = (X, ) — частичное линейное пространство. Скажем, что S строго 1—однородна на С С С, если для любого антифлага (х, L) с L Є С имеем a(x,L) = 1. Аналогично определяется 1—однородность на С С С.
Определим подкласс I класса 1 -однородных частичных линейных пространств, с прямыми размера не более трех. Пусть S — геометрия из I, тогда:
(G1) любая прямая в S имеет размер 2 {короткая) или З(длинная);
(G2) S — 1—однородна на коротких прямых и строго 1—однородна на длинных прямых;
(G3) для любого ребра в TS существует независимое от него ребро этого же графа.
Изучение класса I связано с изучением графов без 3-лап с неклико-выми /х-подграфами.
КРАТКОЕ СОДЕРЖАНИЕ. Диссертация состоит из введения, пяти глав и списка литературы (21 наименования). Во введении обсуждается возникновение и актуальность вопроса, даются основные определения и приводятся основные результаты.
Обозначим посредством К класс связных графов, удовлетворяющих
следующим четырем условиям:
(г) Г не содержит 3-лап;
(г г) всякий р—подграф в Г содержит пару несмежных вершин;
(г г г) Г содержит 3-коклику.
(iv) для любых вершин а, Ъ графа Г условие ах = Ь1 влечет а = Ь.
Настоящая работа посвящена описанию графов класса К.
Пусть х и у вершины графа Г, положим х = у тогда и только тогда, когда х1- = у1. Легко видеть, что = является отношением эквивалентности. Фактор-граф Г графа Г по отношению = будем называть редукцией графа Г, а граф изоморфный редукции некоторого графа — редуцированным. Для графа Г, рассмотрим Г — граф, полученный из Г добавлением в него одной вершины а так, что в Г выполняется равенство a1 = bL для некоторой вершины Ъ из Г. Граф А, полученный из Г посредством конечного числа таких операций, называется кликовым расширением графа Г. Нетрудно заметить, что если граф Г был редуцированным, то он изоморфен редукции А графа Д. Также ясно, что любой нередуцированный граф изоморфен некоторому кликовому расширению своей редукции.
Всякое кликовое расширение графа одновременно с ним удовлетворяет или не удовлетворяет условиям (г) — (г г г ). Следовательно, любой граф, удовлетворяющий условиям (г) — (г г г) является кликовым расширением некоторого графа из класса К.
Выполнение условий (г), (г г) и (iv) для всего графа эквивалентно выполнению этих условий для каждой его связной компоненты. Поэтому вместо того, чтобы требовать наличия 3-коклики в каждой компоненте связности, естественнее считать все изучаемые графы связными.
Пусть 0 — 3-коклика графа Г. Скажем, что граф Г натягивается на 3-коклику 9, если любая вершина из Г \ 0 смежна по крайней мере с двумя вершинами из 0.
В ходе изучения класса К оказалось удобным разбить его на три основных части. Если Г — граф из класса К, то, как не трудно видеть, он удовлетворяет точно одному из следующих условий:
(A) Г содержит 4-коклику;
(B) Г не содержит 4-коклик, но содержит 3-коклику, на которую он не натягивается;
(C) Г натягивается на произвольную свою 3-коклику.
В самом деле, графы из пунктов (А) и (В) не натягиваются на подходя щие 3-коклики, в (В) это указывается явно, а в (Л) достаточно в качестве такой 3-коклики взять тройку вершин из произвольной 4-коклики. Подклассы из К, порождаемые этими условиями, обозначим, соответственно, Кл, Кв, Кс. Графы из класса Кс оказывается естественным разбить на два подкласса, используя следующее условие:
(N) в Г существует3-коклика 9 = {аі,а2,аз}, для которой найдутся вершины h\, h\,h\, h\, h\, hi графа Г такие, что h], hf — несмежные вершины из M(ai,a,i+i) (здесь и далее сложение в индексах происходит по модулю числа его существенно различных минимальных значений), и такие, что подграф Н = {h{\i = 1,2,3; j — 1,2} состоит из пары независимых треугольников.
Зададим теперь разбиение класса Кс на подклассы К# и К#, определив следующие условия:
(D) условие (N) не выполнено;
(E) условие (N) выполнено.
В главе 1 собраны вспомогательные результаты. В главе 2 доказывается следующая теорема (теорема 2.1), дающая описание графов первого из введенных подклассов класса К:
Теорема 1. Если связный граф Г принадлежит классу Кд, то Г изоморфен реберному графу некоторого полного многодольного графа.
Заметим, что реберный граф любого полного многодольного графа, содержащего три попарно независимых ребра, принадлежит классу К.
Пусть Е — полный двудольный граф с долями Е; = {а1,... ,сгт} и Е" = {а\,... ,ап} мощности, соответственно, тип. Граф А = Ь(Е) — т х п—решетка, если 6j = { 7J, 7j}, ТО 5j — вершина графа Л для любых о- 7 Є Е и 7г- Є Е". Максимальные клики графа Л — это в точности множества всех ребер Е, содержащих выбранную вершину из Е. Следовательно, в Л мы имеем два набора попарно непересекающихся клик (прямых) {Дг} и {А-7}, соответственно, из п и т элементов, где Д; = {5\,..., ё™} и Aj = {б{,..., ё{}, для всех i,j таких, что 1 і п и 1 j т. Каждая из вершин графа А определяет пару (определяется парой) клик (прямых), которым она инцидентна (проходящих через нее), то есть АгПА = {5j}. Пусть Л — произвольный граф, изоморфный та х п—решетке А, где Д определен как выше, а р : Д — Л — изоморфизм. Положим \{ = (р(б{), Aj = tp{Aj) и ЛІ = p{Ai), для всех i,j таких, что \ i nw\ j m.
Пусть X С У(Г). Тогда через Xі (соотв. [X]) обозначим множество Р XХ (соотв. Р[х]). Для двух непересекающихся множеств Vi,V2 С хеХ хХ
У(Г) будем писать V\ х V2, если все вершины V\ содержат в своей окрестности множество V2, то есть [Vi] Э V2, или, что эквивалентно, V\ Q [V2]. Если V = {Vi\ 1 і ті] — набор попарно непересекающихся подмножеств множества вершин графа Г, то отношение ; является симметричным и антирефлексивным отношением на V, следовательно, задает некоторый граф на V.
Пусть Д — подграф некоторого графа без 3-лап П, изоморфный q х 3— решетке с q 3. Скажем, что Д связан с дополнением по правилу 6-цикла, если О, \ Д разбивается на три множества Сь С2 и Сз так, что Д,- х Cj и Сг- х Ді+і (индекс по модулю 3) для каждого г, 1 г 3. Заметим, что в этом случае каждое d — клика, а граф О, разбивается на три клики — {Ci U ДІ1 г 3}.
При дальнейшем изучении графов из класса К оказывается, что получить столь исчерпывающее описание, как в случае подкласса К , не сделав дополнительных предположений для оставшихся подклассов из К не удается. Тем не менее оказывается возможным установить некоторые общие структурные свойства, свои для каждого подкласса. Для подкласса К они даются теоремой 3.2, приведем ее формулировку:
Теорема 2. Если связный граф Г принадлежит классу Кв, то Г изоморфен реберному графу некоторого полного многодольного графа, либо для любого подграфа А, изоморфного q х 3—решетке, для некоторого q большего трех, не содержащегося ни в каком подграфе, изоморфном (q + 1) х 3—решетке, связан с дополнением по правилу 6-цикла.
Эта теорема показывает, что граф Г принадлежащий классу Кв является реберным графом, либо разбивается на 3-клики. Иными словами, в этом случае У(Г) = V] U V2 U У3, где Vi попарно дизъюнктны и являются кликами графа Г. Возможности, когда граф Г разбивается на 3-клики и не является реберным, и когда он связан с дополнением по правилу 6-цикла оказываются неразделимыми. Более того, оказывается естественным рассматривать с единых позиций графы из Кд и К#, разбиваемые на три клики. Следующая теорема уточняет результаты предыдущей и, как мы увидим далее, дает часть характеризации класса KD. Следующее определение понадобится нам для ее формулировки. Пусть Ст — цикл длины га, где т — натуральное число, большее двух; натуральные числа 1, 2,...,ki таковы, что кі к2 ••• h \}%\. Циркулянтом C(m;A;i,fc2,... ,&/) называется граф с множеством вершин V{Cm) такой, что две его вершины смежны тогда только тогда, когда расстояние между ними в Ст принадлежит {к\,к2, ...,кі}. Если в качестве вершин цикла Ст выбрать элементы кольца Zm, расположив их друг за другом, то u,v из С(т;к\,к2,...,h) смежны тогда и только тогда, когда и — v Є {±к\,±к2,.. •, ±А;/}. Рассмотрим кликовое расширение графа С(3п; 1,2,... ,п — 1), в котором каждая вершина in + j, где 1 і 3,1 j п, заменена на клику Q(f, j) мощности qj, для некоторых натуральных чисел qi, #2,---, qn. Соединим в этом кликовом расширении вершины каждого объединения М Q(i,j) таким образом, что 1 і 3 бы получилась qj х 3—решетка, и получим граф, который мы обозначим («;9ьф2,.--,9п).
Теорема З.Для любого графа Г принадлежащего одному из классов Кв или Ко и разбиваемого на 3 клики, Г = Q U G, где Q = Q(n;qi,q2,...,qn) для некоторого натурального п и натуральных Я\,Я2,- - - ,Яп больших двух, G — граф, не содержащий 3-коклик, разбиваемый на Зп клик G\,G2,.. .,G n так, что, Gi х М Q{j,k)u jn+k€.[i,i+ 2n—\]
Gi х Gj, если \[i,j]\ п. Более того, в случае п — \, во-первых, некоторые две клики Gi не пусты, если G не пуст, во-вторых, любые две несмежные вершины и є Gi, v є Gj имеют общую смежную в Gk, где {г, j, к} = {1,2,3}, или лежат в G в 4-цикле, в-третьих, любая вершина из d смежна с некоторой вершиной из Gi+i U Gi+2.
Обратно, если G — это редуцированный граф, не содержащий 3-коклик, разбиваемый на три клики G\, G2 и Gz, так, что любые две несмежных вершины и є Gi, v є Gj либо имеют общую смежную в Gk, где {i,j, к} = {1,2,3}, либо лежат в 4-цикле в графе G, а каждая вершина из Gi смежна с какой-нибудь вершиной из Gi+\ U Gi+2, то граф Г, вершинами которого для некоторого q, большего двух, являются вершины графов Q — Г2(1; q) uG.Gi х f2; и f27-+i для каж дого г, а для любого ребра {и, v\, где и Є П(1; q) и v є G, существует г такое, что и Є Gi, v Є fij U Q,i+i, разбивается на З клики, принадлежит Kv, если q = 3, иначе принадлежит Кв. Если п 2 и G — граф, не содержащий 3-коклик, разбиваемый на Зп клик G\, G2, ..., G n, так, что G{ х Gj, если \[i,j]\ п, то граф Г, вершинами которого являются вершины графов Q, = Q,(n;qi,q2,. • ,gn) для некоторого натурального п и натуральных qi.qi,.. • ,qn, больших двух, и G,G{ х М Q(j, к) для каждого і, а для любого
jn+ke[i,i+2n-l]
ребра {u,v}, где и Є Г2 и v є G, существует і такое, что и 6 Gi, v є М Q.(j, к), разбивается на 3 клики, принадлежит клас jn+k€[i,i+2n-l]
су К#, если все qi равны 3, иначе — классу Кв.
Перейдем теперь к результатам, целиком касающимся.класса Кс. Но прежде установим в точных терминах связь этого класса с частичными геометриями.
Лемма 5.28 диссертации каждому графу Д из класса Кс ставит в соответствие некоторую нетривиальную частичную геометрию из класса I. Точечный граф этой геометрии это в точности граф дополнительный к Л. Таким образом, описание классов Ко и Кц эквивалентно описанию таких геометрий.
Теорема 4. Для любого графа Г не разбиваемого на три клики, принадлежащего классу Ко и любого его собственного подграфа Л, изомофного 3 х -решетке, Г = Аи Е U F и Е х F, где А — 3 х 3-решетка, Е и F непустые подграфы графа Г, не содержащие 3-коклик, разбиваемые на три клики, соответственно, Еъ Еч, Ез и F\ F2, F3 так, что Е{ х А{ и Дш и F1 х Д и Аі+\ где 1 г 3, при этом если ЕІ (соотв. F1) для некоторого і содержит вершину v такую, что Vі = Е{в графе Е (соотв. vL — Fl в графе F), то каждая пара Fj, FJ+1 (соотв. Ej, Ej+i) содержит несмежные вершины.
Обратно, если Д — граф, изоморфный 3 х 3-решетке, а Е и F — это непустые графы, не содержащие 3-коклик, разбиваемые на три клики, соответственно, Е\, Е2, Е и Fl, F 2, F3 такие, что любые две различные вершины из Е{(соотв. Fi) имеют различные окрестности в Е (соотв. F), если Е( (соотв. Fi) для некоторого і содержит вершину v такую, что vL = Еів графе Е (соотв. v1- = Fi в графе F), то каждая пара Fj, FJ+1 (соотв. Ej, Ej+-[) содержит несмежные вершины, то граф Г такой, что V{T) = V(A) U V(E) и V(F), а Е(Г) кроме ребер трех выбранных графов содержит те и только те ребра, которые необходимы для выполнения следующих условий: ЕІ х Дг- и Ді+Ь F{ ж Лі U Аг+1 для всех l i 3uE F, принадлежит классу Кд.
Следующие определения нам необходимы для формулировки теоремы, описывающей графы из КЕ. Для каждого і такого, что 1 і 3, все графы получающиеся из Т(б) удалением і попарно несмежных вершин изоморфны между собой. Рассмотрим теперь произвольный куб С в R3. Рассмотрим полный граф Ф, вершинами которого являются грани куба. Обозначим L0 = Ь(Ф). Удалим из Ь(Ф) г попарно несмежных вершин, где 1 г 3, а именно і ребер Ф, соединяющих противоположные грани куба, обозначим получившийся граф Ь(. Поскольку каждый /z-подграф в Т(б) изоморфен 4-циклу, то удалив г-коклику, где 1 і 3, мы получим граф с некликовыми / -подграфами. Выполнение же условий (г), (ггг), (iv) и (Е) для такого графа очевидно. Таким образом каждый из графов Li принадлежит К, где 0 і 3. Для каждого натурального і из [1,6] для грани d куба С естественным образом определена противоположная грань, ее номер обозначим і. Вместо символа {СІ, CJ] для неупорядоченной пары граней мы будем использовать символ (ij).
Пусть Д — связный граф, натягиваемый на любую свою 3-коклику, содержит подграф S, изоморфный L3. Пусть — подграф графа Д, содержащий граф Е, максимальный относительно свойства быть изоморфным подграфу из LQ. Для вершин Е будем использовать те же обозначения, что и для вершин графа LQ, которые ставяться им в соответствие изоморфизмом соответствующих графов. Предположим, что для любой вершины v из Д \ Е существует такое целое і из отрезка [1,0], что v смежна с теми и только теми вершинами (jk), что і g {j, к], для каждого і посредством Ut обозначим множество таких вершин v. Про вершины из Ui будем говорить, что они принадлежат г-ой грани. Положим U = [J t/j = А \ Е . В соответствии с тем, какому из графов L2- изо i j a морфен подграф Е графа Д, граф Д будем называть U—расширением графа Lj. Нетрудно показать (пункт (1) леммы 5.19), что для всех г и j в каждом [/—расширении графа Lt, принадлежащем К, подграф Uj — клика. Для графа Д определим граф W следующим образом, положив, V(W) = V(U),E(W) = E(U)\ U Е(и{). i i 6
Теорема 5. Если связный граф Г принадлежит классу КЕ, то выполнено одно из следующих утверждений:
(1) Г является подграфом графа Шлефли;
(2) Г изоморфен U—расширению графа Ьр для некоторого р большего 0, такому, что Lp не содержит (И), и U = Ui U U\ для некоторого і, при этом каждая вершина из Щ смежна с некоторой вершиной из Щ и наоборот, для любых двух вершин из U, лежащих одновременно в Ui или Щ, их окрестности в U различны;
(3) Г изоморфен U—расширению графа Ь$, в Uk U Щ = 0 для некоторого к, при этом если і и j таковы, что {i,j,k} U {i,j, k} = {1,2,..., 6}, то (Ui U Щ) П W = L\ U L\ U ... L) U U и [Uj U Щ) П W = L\ U L32 U ... L\ U LP для некоторого натурального l, где каждый из объединяемых в правых частях равенств подграфов является связной компонентой левой части соответствующего равенства, каждое L\u LPS — 2-клика, для каждого s вершины L\ не смежны в Uj U Щ только с вершинами L?s, вершины из U смежны со всеми вершинами в Uj U Up любые две вершины как графа U, так и графа LP, одновременно принадлежащие Uq для некоторого q, имеют в этих графах различые окрестности;
(4) Г изоморфен U—расширению графа Lp для некоторого р большего 0, такому, что для некоторых i,juk таких, что {i,j, k}U {г, j, k} = {1,2,..., 6}, Lp не содержит (гг), и множества Uit Uj и Uk не пусты, W состоит из двух компонент связности W\ и W-2, W\ является 2-кликой, одна из вершин которой принадлежит Ui, а другая Uj, любая пара несмежных вершин из W2, не лежащих одновременно в U\ ни для какого I, лежит eUiU Щ, любые две вершины из W-2, принадлежащие одновременно Ui либо Щ, имеют различные окрестности eW2n [Ui U Uj);
(5) Г изоморфен U—расширению графа Lp для некоторого р, большего 0, и для некоторых i, j и к таких, что {i,j, к} U {г, j, к} = {1,2,..., 6}, множества Ui, Uj и Uk не пусты, любые две вершины в U принадлежащие Uq и Ur таким, что г $ {q, q} смежны, если содержит вершину (ss) для некоторого s, то подграф Us U /5 является 1-кликой либо 2-кликой, причем в случае когда Us U С/5 — 2-клика, одна ее вершина принадлежит Us, а другая U5, и для любого t из {1,2,..., 6} любые две вершины из Ut имеют в W П (Ut U Щ различные окрестности.
После структурных результатов оказывается естественным указать результат, в котором при дополнительных условиях удается полностью описать строение. Такое описание удается получить лишь для той части графов из К, каждая вершина которых лежит в них в некоторой 3-коклике. Из теорем, описывающих подклассы из К, легко следует следующая теорема:
Теорема 6. Связный граф Г из класса К, каждая вершина которого лежит в 3-коклике, изоморфен реберному графу некоторого полного многодольного графа либо изоморфен графу (п; 7ь 92? • • •, Чп) где каждое qi — натуральное, большее двух, либо является подграфом графа Шлефли.
Учитывая соответствие между графами из Кр и КЕ и подклассом класса всех частичных геометрий, мы получаем, что предыдущая теорема, в частности, дает описание частичных геометрий из класса І, в которых каждая точка лежит на некоторой длинной прямой.
Пусть S = (X, С) — частичное линейное пространство. Пусть также Xі С X и С = {LnX \L Є С А \Ы)Х \ 2}. Геометрия S = (Х ,) является частичным линейным пространством. Назовем S естественным подпространством пространства S.
Геометрию из класса I, дополнительный граф которой изоморфен графу Q,(n;qi,q2,... ,qn), где все qi равны 3, обозначим CG{n) и назовем циркулянтно-решетчатой геометрией.
Имеем:
Следствие. Пусть геометрия S принадлежит классу 1, а каждая ее точка лежит на некоторой длинной прямой. Тогда S изоморфна циркулянтно-решетчатой геометрии CG(n) для некоторого натурального п, либо является естественным подпространством геометрии GQ(2,4).
Графы, содержащие 4-коклику
Доказательство. Для сокращения записи вместо Х\, Y\ и Z\ будем писать X,Y и Z, соответственно. Причем для обозначения произвольной вершины из XUYUZ мы будем использовать одну из букв х, у или z, возможно с некоторым индексом, в соответствии с тем, какому из множеств X, Y или Z она принадлежит. Этого правила мы будем придерживаться на протяжении всего доказательства настоящей леммы.
По пункту (2) леммы. 1.5 и пункту (1) леммы 1.8 для любой вершины из У существует не более чем по одной несмежной вершине как в X, так и в Z.
1. Допустим в Y есть вершина у такая, что существуют несмежные с ней вершины ху Є X и zy Є Z. Тогда по пункту (2) леммы 1.5 вершины ху и zy смежны со всеми вершинами из У \ {у}, a yL Э (X \ {ху}) U (Z \ {zy}). Также заметим, что ху zy, поскольку ху, у, zy лежат в окрестности вершины Ъ.
Предположим, что У \ {у} ф 0, пусть у є У \ {у}, тогда, как отмечено в пункте 1 доказательства настоящей леммы, у ху и у zy.
Допустим у — смежна со всеми вершинами из объединения / -подграфов М(а,Ь) и M(d,h). В таком случае можно утверждать, что X = {ху} и Z = {zy}. Действительно, всякая вершина х из X \ {ху} смежна с вершинами уиу,а потому, дважды применив лемму 1.11, получим у1 П Z = х1- П Z = yL П Z. С другой стороны, вершина zy смежна с у и не смежна с у. Полученное противоречие доказывает, что X = {ху}. Аналогично, Z = {zy}.
Таким образом, если У = 2, то подграф X U У U Z — это подграф графа треугольной призмы, приведенный на рисунке 16. Если же У 3, то любая вершина из У \ {у}, в том числе у, смежна с ху, у, zy. А потому подграф X U У U Z, является кликовым расширением графа на рисунке 16, в котором вершина у заменена на клику мощности не меньшей двух. Иными словами X U У U Z — подграф из пункта (2) настоящей леммы. 1.1.2. Предположим теперь yL не содержит объединение //-подграфов М(а,Ь) и M(d,b). Без ограничения общности будем считать, что существует Ху є X, такая что Ху -/- у. Очевидно, что Ху ф ху. По пункту (2) леммы 1.5 Ху у. Применив лемму 1.11 к паре Ху и у, получаем Ху Zy. Отсюда следует, что \У\ = 2, поскольку произвольная вершина в У \ {у, у], в силу пункта (2) леммы 1.5, обязана быть смежной с ху и zy, а значит, по лемме 1.11 должны быть смежны и Ху с zy, противоречие.
Покажем теперь, что Х = 2. Допустим Х 3 и х Є X \ {ху,ху}, тогда по пункту (2) леммы 1.5 вершина х смежна со всеми вершинами из У. Из леммы 1.11 следует, что х и все вершины из У смежны с одними и теми же вершинами из Z. Это противоречит тому, что у fi zy у. Аналогично показывается, что \Z\ 2. Причем если \Z\ = 2, то вершина из Z, отличная от zy, смежна с у. Поэтому она, в силу леммы 1.11, обязательно не смежна с и смежна с ху. Следовательно, по.лемме 1.11 эта вершина не смежна с у. Наконец, осталось заметить, что Z — клика по лемме 1.11. Подграф X U У U Z для случаев \Z\ = 1 и \Z\ = 2 — это в точности подграф графа треугольной призмы, приведенный на рисунках 1в и 1а, соответственно.
1.2. Рассмотрим случай \У\ = 1. Согласно пункту (2) леммы 1.5, лемме 1.6 и пункту (1) леммы 1.8 любая вершина из X \ {ху} содержит в своей замкнутой окрестности /z-подграф М(а,Ь), а любая вершина из Z \ izy} — / -подграф M(d, b). Кроме того, по лемме 1.11 все вершины из X \ {ху} смежны со всеми вершинами из Z\{zy}, а такжеху Z\ {zy} и X \ {ху} ф zy. Теперь легко видеть, что для любой вершины х є X \ {ху} выполнено: х1 П (X U У U Z) = X U У U (Z \ {zy}). Докажем теперь, что Х \ {ху}\ 1. Допустим противное, х и х — различные вершины из X \ [ху]. Так как Г редуцирован, то согласно лемме 1.4 из различия вершин хих следует различие их окрестностей в Л. Из определения X, лемм 1.1, 1.6, 1.9 и того, что х1 П (X U У U Z) = xL П (X U У U Z), вытекает, что в А окрестности вершин хих могут различаться лишь в М(Ь, с). Поскольку х,х, zy Є [6] и {х,х} ф zy, то М(Ь, с) \ [zy] С [х] П [х]. Более того, [zy] П [х] П M(b,c) = [zy] П [х] П M(b,c) = 0, поскольку М(Ь,с) С [с] и вершины в тройках x,zy,c и x,zy,c попарно несмежны. Откуда [х] П М(Ь, с) — [х] П М(Ь, с), а, значит, х = х, противоречие. Аналогично доказывается, что \Z \ {zy}\ 1. Заметим, что ситуации Х = 2, \Z\ = 1 и \Х\ — 1, \Z\ = 2 симметричны. Поэтому здесь мы получаем три различных подграфа графа треугольной призмы — это подграфы на рисунках 1г, 1д, 1е. Они соответствуют следующим случаям: \Х\ = 1 и Z = lfX=2HZ = l,X = 2HZ = 2.
2. Рассмотрим теперь случай, когда каждая вершина из У смежна со всеми вершинами из X U Z за исключением быть может одной вершины. Тогда, очевидно, существуют различные вершины у, у є Y, такие что существуют ху Є (ХП [у]) \ [у] HZy (ZD [у]) \ [у]. Пользуясь леммой 1.11, как и в части 1 доказательства, можно показать, что X U Y U Z состоит из только что перечисленных вершин, и Ху /- Zy, у у. Соответствующий подграф графа треугольной призмы приведен на рисунке 1ж. Лемма доказана.
Следующее утверждение является непосредственным следствием леммы 1.12. Следствие. Если /z-подграф вершин а и Ь содержит треугольник, то минимум две его вершины лежат в УЇ. Лемма 1.13. Справедливы следующие утверждения: (1) любые две вершины х\, Щ из Х\ не имеют общих смежных вершин из М(6, с); (2) любые две вершины у\ иуї из Y\, из которых хотя бы одна не содержит в своей замкнутой окрестности все множество М(а, b)U M(d, b), не имеют общих смежных вершин из М(Ь, с). Доказательство. (1) В силу леммы 1.12 в случае, когда Xi 2 мы имеем \Х\\ = 2 и существует вершина z\ в Z\, такая что \z П Xi = 1. Без ограничения общности можно считать, что z{ содержит х\. В этом случае х{ П М(Ь, с) = Zi П M(6, с), поскольку а смежна с x\ и не смежна ни с z\, ни с какой либо вершиной из М(Ь, с), и, симметрично, d смежна с z\ и ііПМ(6, с) = 0.Для завершения доказательства (1) осталось заметить, что Щ1- и zj1 не пересекаются в М(6, с), так как хї н z\№ смежны между собой и с вершиной с.
Графы, не натягиваемые на некоторую 3-коклику
Последний шаг в (II) — это рассмотрение вершин из М(Ь,с). Взяв в качестве базовой четверки вершины {6, с, d,xy} и применив лемму 1.12, мы видим, что в М(Ь,с) не больше двух двухэлементных долей (говоря так, мы рассматриваем этот подграф, как полный многодольный граф с долями из одной и двух вершин). В случае же, когда двухэлементных долей две, в М(Ь, с) нет одноэлементных долей. Рассмотрим теперь два случая: в М(Ь, с) одна или две двухэлементных долей. Сначала рассмотрим второй случай. Опишем смежности вершин подграфа А, построенного по базовой четверке {а, 6, с, d] графа Г, с вершинами из М(Ь,с). Пусть w\,w2 и щ,и2 — это вершины первой и второй двухэлементных долей в М{Ъ,с). Понятно, что можно считать, что {w\,u\} С у1, {w2,u2} С Ху, { 2, } С z, {wi,u2} С у1, {w2,in} С аг, {гп2,щ} С z, {w2,u2} С if и {w2,U{} С .f, для произвольных ti Є УЇ \ {у} и t2 Є Y2 \ {у}. Это единственно возможный случай, с точностью до переобозначения вершин из М(Ь, с). Единственность здесь — следствие запрета на наличие 3-лап. Рассмотрим /і-подграф вершин zy и щ. Он, как нетрудно видеть, состоит из смежных вершин b и w2, то есть полон, и в рассматриваемом нами случае нет графов, удовлетворяющих условию теоремы.
Предположим, что в М(Ь, с) имеется одна доля, состоящая из двух вершин щ,и2. Снова нетрудно видеть, что с точностью до переобозначения вершин из М(Ь, с), должно быть щ Є Ху Г) Zy1 П yL и и2 Є х± П гф Г) у1. Так же, как мы не раз видели, t± П М(6, с) С х и t П М(6, с) С х±, для произвольных t\ из Yi \ {у} и t2 из Y2 \ {у}. Пусть w Є M(b, с) \ {щ, и2}, тогда либо {2/,27} С ги1, либо {xy,zy,Xy,Zy} С wL. Первое невозможно, поскольку оно влечет, что w1 не пересекает (Уі \ {у}) U (Y2 \ {у}), следовательно, в у1 содержится три попарно несмежных вершины г/1, у2, w, что невозможно. Значит, выполняется второе. Теперь нетрудно видеть, что подграф Л на вершинах {a, d0,..., dk, у, у; ху, xdy\ ..., xdyk,b, ицху, xf,... xf, с, и2] — (к+ 4) х 3-решетка, где точкой с запятой разделены 3 прямые размера (/: + 4). Эти прямые мы обозначим Ль Л2 и Л3. Если теперь мы положим d = M{a,b) \ {у,ху}, С2 = M(a,b) \ {y,xv} и С3 = М{Ъ,с) \ {щ,и2}, то получим, что СІ х ЛІ х Cj+ь то есть что Л связан с дополнением по правилу 6-цикла. Более того, как легко видеть Л не лежит ни в каком большем подграф, изоморфном т х п—решетке для любых параметров тип. (III) Итак, мы видим, что если Г удовлетворяет условиям (1) или (2) из пункта (II), то мы уже имеем некоторую информацию о его структуре. Докажем, что если в Г есть /і-граф, содержащий треугольник или подграф, изоморфный Рзт то выполняется одно из условий (1), (2) из (II). 1. Пусть и\\\и2 — вершины на расстоянии 2 в Г и вершины v\,v2, v$ из М(и\,и2) образуют треугольник. Если ui и и2 содержатся в некоторой базовой четверке, то мы имеем (1) из (II). Поэтому далее можно предполагать противное. 1.1. Рассмотрим случай, когда одна из вершин щ и и2, без ограничения общности ui, содержится в некоторой базовой четверке {a,b,c,d}. Нетрудно видеть, что можно считать щ = а. Из (I) нам известно представление Г в виде объединения подграфов, построенных по базовым четверкам и паре вершин, неизменно участвующих в этих четверках. Пусть две последние вершины — это 6 и с, a {a,dQ,d\,... ,е/ }, где d0 = d и к 0, — множество вершин некоторой клики, максимальной относительно свойства — быть изолированной от Ъ и с. Покажем, что и2 лежит в М(Ь, с). Допустим это не так. Тогда и2 содержится либо в bL П {dj- \ ах), либо в сх П (dj- \ а1-) для некоторого 0 I к. В обеих ситуациях щ и и2 попадают в некоторую базовую четверку. Итак, и2 лежит в М(Ь,с). В таком случае вершины V{ лежат в М(а, b) U М(а, с), поэтому, без ограничения общности, две из них лежат в М(а,Ь), причем можно считать, что третья тогда — обязательно в М(а, с), иначе имеем (I) из (II). А это в свою очередь возможно только, если все Vi одновременно лежат или не лежат в окрестности вершины d. Представляется две возможности: \{a±\d±)Db-Ln{v],v2,v3}\ = 2 и \aL П dL П Ь1 П {ui,v2,v3} = 2. Тогда две вершины либо из (a±\d-L)Db±, либо H3a-Lnd-Ln6J- смежны с одной и той же вершиной и2 из М(Ь, с), что либо противоречит лемме 1.13, либо в а1Пс?1ПЬ1 содержится больше одной центральной вершины, и мы имеем, что выполнено условие (1) из (II). 1.2. Пусть теперь ни одна из вершин щ и и2 не лежит ни в одной базовой четверке. Пусть {а, 6, с, d} — некоторая базовая четверка, {a, do, d\,..., dk} — максимальная клика, изолированная от Ъ и с в Г. В таком случае обязательно {щ,и2} Я а-1 П d П df П dj:, и мы имеем условие (2) из (II). 2. Пусть щ и и2 — вершины, лежащие на расстоянии 2 в Г, а вершины г ъ 2 з из М{щ,и2) таковы, что v\ v2 и v$ Ф {v\,v2}, то есть вершины Vi порождают Рз- Согласно лемме 1.5 вершины щ и и2 не лежат в 3-коклике, тем более в базовой четверке. Аналогично пункту 1 пункта (III) мы заключаем, что если одна из вершин щ, без ограничения общности щ, лежит в базовой четверке {а, 6, с, d}, то и2 лежит в М(6, с). Здесь возможны два случая: «i, v2 лежат вместе в одном из /і-графов М(а, 6), М(а, с), и в разных. В первом случае v\ и v2 обязаны одновременно лежать или не лежать в d1, поэтому не могут быть смежны с одной и той же вершиной из М(Ь,с), что следует из леммы 1.13, для применения которой мы снова замечаем, что либо выполнено условие (1) из (II), либо число вершин каждого из подграфов М{а, Ъ) U M(d, b) и М(а, с) U M(d, с), содержащих этот подграф в своей замкнутой окрестности, не превосходит единицы. Во втором случае г з попадает в один д-подграф М(а,6) или М(а, с) с одной из вершин v\ или v2, следовательно, в силу пункта (1) леммы 1.5, не может быть смежна вместе с ней с вершиной и2, которая лежит в М(Ь, с). Ситуация, когда ни одна из вершин щ и щ не лежит ни в одной базовой четверке, совершенно аналогична 1.2 пункта (III).
Заметим теперь, что /х-подграф любой пары вершин Г, лежащих на расстоянии 2, не содержит треугольников и подграфов, изоморфных Рз, означает, что в Г нет подграфов, изоморфных Н\ и Н2. А значит пользуясь леммой 1.15, мы получаем, что, если Г не содержит q х 3—решетку, связанную с дополнением по правилу 6-цикла, то он является реберным графом. Сейчас для завершения разбора настоящего пункта достаточно воспользоваться леммой 1.17.
(IV) Предположим, что Г не является реберным графом. Тогда, как уже доказано для некоторой базовой четверки выполнено одно из условий (1) или (2) из (II). Тогда, как уже доказано существует подграф Л, изоморфный q х 3—решетке с q 4, связанный с дополнением по правилу 6-цикла. Выберем произвольный подграф А, изоморфный г х 3— решетке, для некоторого г большего трех, не содержащийся ни в каком подграфе, изоморфном (г +1) х 3—решетке. В таком случае, в силу леммы 1.21 либо Д содержится в Л и, что следует из условия, совпадает с ним, либо не пересекает. Первое дает утверждение настоящей леммы, поэтому разберем второй случай. В этом случае, для любой базовой четверки из А / -подграф произвольной пары несмежных вершин из нее содержит Aj для некоторого г", а значит для этой базовой четверки выполнено утверждение (1) из (II). Это влечет, что эта базовая четверка содержится вр х 3—решетке Е, связанной с дополнением по правилу 6-цикла. Пользуясь леммой 1.21 получаем, что Д = . Этим доказано, что Д связан с дополнением по правилу 6-цикла. Теорема полностью доказана.
Графы, разбиваемые на три клики
Следовательно, Г удовлетворяет заключению лем мы 5.13, а значит, и настоящей леммы. Предположим теперь, что все синие и красные вершины из М2 смежны с вершинами ребра Р\а3. Пусть 2 и / — произвольные вершины из М-2, первая из которых красная, а вторая синяя. Тогда выбрав тот же подграф Ф, кроме того, что pi = 7 , Р2 = 5N, g3 = 4N, Рз = SN, р\ = 2N, также будем иметь, что а2 = 2е, а р-2 = 3е. Рассмотрим подграф Г\ (0еU5е) и его подграф Фи [J PN. По pezg скольку каждый подграф {Iе 2N,8}, {3е, 4", 1}, {4е, 5 ,2}, {6е,7л ,4}, {7е, 8 5}, {8е, AN, bN}, {2е, 7 , 8N} — либо 3-коклика, либо 2-коклика в Г \ (0е U 5е), то эта пара подграфов удовлетворяет условию леммы 5.13, следовательно, Г \ (0е U 5е) удовлетворяет ее заключению. Рассмотрим теперь граф Г и его подграф Г \ (0е U 5е), поскольку {0е, 2е, 8} и {5е, 3е, 0} — потенциальные 3-коклики, то рассматриваемая пара удовлетворяет условию леммы 5.13, следовательно, Г удовлетворяет ее заключению. Этим пункт (1) полностью исследован. (2) Как в предыдущем пункте, пользуясь леммой 5.5 выберем несмежные вершины QI є Мі и аз Є Мз, и несмежные вершины Р\ Є М\ и Рз Є М3. Как и в пункте (1) возможны два случая: первый состоит в том, что ai смежна среди трех оставшихся только с /?ь а вершина аз — с Рз, второй — рассматриваемые четыре вершины соединены в точности двумя ребрами, а именно, а\Рз и з/?і- Можно непосредственно убедиться, что первый случай рассматривается совершенно также как и в (1). Рассмотрим второй случай. В качестве подграфа Ф выберем подграф {ai, ai, 1,02,92, «а, аз, схз,Рз}- Имеем: р1 = 7N,p2 = 5", Яз = 4 \ / = 8N, /?i = 2 , более того, к 2 = lN. Следовательно, к потенциальным 3-кокликам перечисленным в (1), которым принадлежат вершины 2N, 4N, bN, 7N, 8N, прибавляется {5C, 1 , 2 } и {0е, 1N, 7}. Рассмотрение данного случая заканчивается применением леммы 5.13 к паре Г и Фи j J PN. (3) Рассмотрим подграф Ф на вершинах {ai,ai,gi,a2,92, 2» аз аз»Рз}» где Q! и аз — произвольная пара несмежных вершин из /і-подграфа М(аі,р2), из леммы 5.5 следует, что это красные вершины, причем не ограничивая общности можно предположить, что ai Є a (Мі) и аз Є а(М3). Нетрудно видеть, что р\ = 7N, р2 = 5 , qr3 = 4N, к[ = 8е. Пользу ясь леммой 5.5 получаем, что существует пара несмежных вершин (32 и /?з, соответственно из /3{М2) и /?(Мз). Как в двух предыдущих пунктах под граф П = {с ъ/?2,с з»/?з} состоит из двух независимых ребер. Возможны в точности два случая: либо а\ смежна с /. либо ai смежна с /. Рас смотрим первый из них. Имеем: / = 1е и / = 6 . Оказывается, что в этом случае для Г выполнено утверждение (с) теоремы 5.2. В самом деле, рассмотрим в Г 3-коклику {a\,q2}p2}, рассмотрим также пару треуголь ников {к\,а2,схі} и {аз,аз аз}- Треугольники независимы, это проверя ется непосредственно. Первый из этих треугольников пометим красным цветом, а второй синим. Также имеем, что каждый из этих треугольников пересекается с каждым /і-подграфом выбранной 3-коклики по одноэле ментному множеству. Более того, вершины /?2, Рз и рз являются коричне выми левыми. Наконец, рассмотрим ситуацию, когда в графе П смежны вершины Q] с / и / с аз. В этом случае имеем: / = 2е и / = 8 . Тогда имеем, что любая вершина из 0е дополняется до 3-коклики вершинами fa = 2е и 8 = рз, 1е — 8е и 7, 2е — 7N и 8", 3е — 4N и 1, 4е — 5 и 2, 6е — 7 и 5, 7е — 8 и 6, 8е — 4 и 5 . Используя лемму 5.13 для Г\(1си2сги5с)иГ\ [J Рс, доказываем сначала, что Г\ (1еU2еUЪс) удовлетворяет заключению этой леммы. Затем, используя ту же лемму для Г \ 5е и Г \ (2е U 5е U 1е) доказываем, что первый удовлетворяет ее заключению, а затем как и в (1) используем 5.8 для доказательства того, что Г вкладывается в граф S в соответствии с Ф. (4) В силу леммы 5.5 существует пара несмежных синих вершин (32 и Дз, первая из которых лежит в М2, а вторая в Мз- В качестве подграфа Ф выберем подграф на вершинах {ai,pi,Ki,a2,/?2, 72,аз,/?з,Рз}, метки из Z9 произведем соответственно порядку записи. Имеем: qi = 2 , р2 = 1 , 5з = 4 и к2 = Iе. Снова пользуясь леммой 5.5 получим, что существует пара несмежных красных вершин а\ и а2, первая из которых лежит в Мь а вторая в М2. Как в предыдущих пунктах подграф П = {аь р2, «2, /} состоит из двух независимых ребер. Возможны в точности два случая: либо ai смежна с /. либо ai смежна с р2. Рассмотрим первый из них. Если мы теперь выберем 3-коклику G = {аз, а2, а{] и те же треугольники и с теми же цветами, то получим, что вершина к\ станет коричневой правой и вместе с а\ окажется в М\(аз,а2,аі), вершина / окажется в М2(а ,а2, ai), а а2 и / окажутся в Мз(аз,а2,аі). В пункте (3) настоящей леммы доказывалось, что этот граф содержит такую 3-коклику и пару треугольников, для которых существует 3 коричневых одной ориентации, то есть в рассматриваемом случае выполнено утверждение (с) из заключения теоремы 5.2. Рассмотрим теперь случай, когда а\ смежна с f32. Из леммы 5.5 следует, что существует пара несмежных вершин, первая из которых принадлежит Р{М{), а вторая Р{М$). Предположим, сначала, что вторая из них — это вершина /. Первую обозначим /. Тогда ясно, что Pi смежна с /. Имеем, что pi = 0е. Теперь, пользуясь леммой 5.13 для пары r\(2cU3cU4cU6cU7cU8c) и Г\ (J Рс .доказываем, что первый удовлетворяет ее заключению. Далее используем ту же лемму последовательно дляпарГ\(и4сибс)иГ\(2сиЗси4сибси7си8с),ГиГ\(и4сиб). В результате получаем, что Г изоморфно вкладывается в граф Шлефли в соотвествии с Ф. Предположим теперь, что существуют несмежные вершины Рі є Р{Мі) и / є Р(Мз) \ {/}. Тогда / смежна с /. а следовательно, в силу леммы 5.8 и того, что {pi, р2, /} — 3-коклика, смежна и с р2. Откуда сразу следует, что / не смежна с а2, а это в свою очередь влечет, что Рз смежна с аь Аналогично, получаем, что / смежна с а2 и /?з, не смежна с Qi и р2. Рассмотрим теперь для 3-коклики {аі,а2?аз} новую пару треугольников — ос\р2рз и P\q2q$. Тогда будем иметь, что вершины к\, а2 и / являются коричневыми одной ориентации, а следовательно для Г выполнен пункт (с) из заключения теоремы 5.2. (5) Доказательство проводится совершенно аналогично пункту (3) в части когда выбранные аналогичным образом вершины а\ и р2 смежны. Случай когда смежны вершины а\ и / отличается лишь тем обстоятельством, что АСЗ = 4е, но это не влияет ни на одно из трех применений леммы 5.13. Это означает, что доказательство дословно переносится. (6) Как и раньше пользуясь леммой 5.5 выберем пару несмежных красных вершин, первая из которых аі Є Мь а вторая аз Є Мз. В качестве подграфа Ф выберем подграф на вершинах {аі,аьді,а2,42,4 аз,аз,Рз}.Имеем:рі = jN 2 = IQ3 = AN,K[ = 8е,
Графы, натягиваемые на любую 3-коклику
Предположим, что U = UiUU-it для некоторого целого і из [1,6]. Тогда каждая вершина v в силу условия (п) и пункта (1) леммы 5.20 обязана быть смежной с вершиной из противоположной грани. Условие редуцированности, как нетрудно видеть эквивалентно тому, что любые две вершины как из Uj, так и из Щ имеют в W различные окрестности. При этом в силу пунктов (2) леммы 5.20 не содержит вершину (и). Как нетрудно видеть это соответствует пункту (1) из формулировки настоящей леммы.
Предположим, что U = Ui U Щ U [/&, где А; $. {г, г } и {г, г, к} С {1,2,..., 6}. Используя лемму 5.24 получаем, что W содержит не более двух компонент связности. Предположим, что W состоит из двух компонент связности — W\ и W2. Предположим, что и W\ и W2 пересекают Uj для каждого j Є {і, і, к}. Тогда, применяя пункт (2) леммы 5.19, получаем, что любые две вершины из W\, принадлежащие разным граням смежны. Учитывая условие (iv) и то, что W\ и W2 независимы, получаем, что Wi пересекает каждую грань не более чем по одной вершине и является кликой для обоих значений /. Следовательно, имеет место пункт (2) из формулировки настоящей леммы. (2.1.2) Предположим, что одна из компонент пересекает только две грани, тогда в силу пункта (1) леммы 5.20 это противоположные грани — г-я и г -я. Отсюда следует, что вторая пересекает все три грани. Пусть без ограничения общности первая — это W\, вторая — W2. Как в пункте (2.1) доказывается, что W\ — клика, и W2 П (Ut U Uk) и W2 П (/- U Uk) — полные двухдольные графы. Из последнего вытекает, что Д = 1. Учитывая пункт (1) леммы 5.19 получаем, что W\ — это в точности ребро, а в графе W\ П (Ui U Uj) каждая компонента связности содержит по крайней мере две смежные в W вершины. Более того, в силу пункта (2) леммы 5.20, примененному к произвольной вершине из W\, граф Е не содержит вершину (гг). С другой стороны, из пункта (1)той же леммы следует, что вершина (п) должна существовать. Следовательно, этот случай не возможен. (2.2) Рассмотрим теперь возможность, когда W связен. Во-первых, заметим, что в силу пункта (1) леммы 5.22 подграф содержит вершину (и). Отсюда и из пункта (2) леммы 5.20 в свою очередь следует, что любая вершина из Ui U Щ смежна с некотрой вершиной из Uk. Вместе с тем, из пунктов (2) и (4) леммы 5.19 следует, что смежны любые две вершины, одна из которых лежит в Ui, а другая в Щ, как одновременно смежные с произвольной вершиной из Uk, так и одновременно несмежные с такой вершиной. Более того, с учетом того, что в силу пункта (1) леммы 5.20 каждая вершина из Ui U Щ смежна с некоторой вершиной напротив, из (3) леммы 5.19 следует, что для любой вершины v из Uk в графе W множество вершин из U{ U Щ смежных с ней и не смежных с ней в W образуют компоненты связности графа W П (Щ U Uj). Учитывая, что вершины каждой компоненты связности графа W П (Щ U Uj) с одними и теми же вершинами в Uk, а также редуцированность Г, получаем, что выполнено утверждение (2) из заключения настоящей леммы.
Рассмотрим теперь случай, когда U = UiUUjUUjUUj, те j {г, г}. Для вершины v из Ui рассмотрим подграф (Uj U Щ) \ [v] в U. Как следует из пунктов (1) и (2) леммы 5.19 любые две вершины в нем, лежащие на разных гранях, смежны. Отсюда следует, что если этот подграф содержит вершины с разных граней, то он является полным двудольным графом. Более того, в этом случае в силу пункта (3) леммы 5.19 вершины этого подграфа образуют компоненту связности в подграфе W ( \(UjUUj). Аналогично для вершины v из Uk, где к б i,j,j.
Предположим, что подграф Е не содержит вершин (И) и (jj). Тогда, как следует из пункта (1) леммы 5.19 каждая вершина из U смежна с некоторой вершины из грани напротив. Нетрудно видеть, что для любого к из {i,j,i,j} вершины произвольной компоненты связности S подграфа W Г) (Uk U Uk) графа W смежны с одними и теми же вершинами в W \ (Uk U Щ). Положим U W.D — объединение компонент связности, соответственно, подграфа W П (Ui U Uj) и подграфа W П (Uj U Uj) графа W, вершины которых смежны в нем соответственно со всеми вершинами из Uj U Uj и Uj U Uj. Из замечания, сделанного в начале пункта (3) и того, что каждая вершина U смежна с некоторой вершины из грани напротив, мы имеем, что каждая компонента связности S подграфа Wf) (Ui U Щ) графа W, не лежащая в U, в пересечении окрестностей своих вершин с Uj U Щ содержит некоторую компоненту связности R подграфа Wn(UjUU]) графа W, содержащую по крайней мере две смежные вершины. Более того, поскольку R является полным двудольным графом и ее вершины смежны с одними и теми же вершинами в Uj U Uj, то любые две ее вершины име ют одинаковые окрестности в W. Отсюда, из определения W и пункта (1) леммы 5.19 следует, что их замкнутые окрестности в Г совпадают. Следовательно, R — 2-клика. Замечаем наконец, что R состоит из тех и только тех вершин, которые не смежны с некоторой, а значит, и любой вершиной S. Теперь нужно отметить, что поскольку S является компонентой связности подграфа W П (Ui U Щ) графа W, то она совпадает с объединением доплонений до окрестностей вершин из Л в подграфе W П (Ui U Uj) графа W, а также с пересечением этих дополнений. Этим доказано, что S — 2-клика. Аналогично рассуждения проводятся и для произвольной компоненты связности подграфа Wf](Uj\JUj) графа W. В итоге мы получаем, что W П (Ui U Uj) \ U состоит из I компонент связности L ., не лежащих в U, каждая из которых является 2-кликой, а все ее вершины не смежны в W П (Uj U Uj) в точности с вершинами некоторой компоненты связности этого подграфа из W. Этим доказано, что при I 1 имеет место пункт (3), а при I = 0 пункт (5) из заключения настоящей леммы.
Предположим теперь, что некоторая вершина из U не смежна ни с какой вершиной из грани напротив. Не ограничивая общности предположим, что эта вершина принадлежит Ui, обозначим ее и. Тогда в силу пункта (1) леммы 5.20 содержит вершину (jj). Отсюда и из пункта (4) леммы 5.19 следует, что любые две вершины из окрестности произвольной вершины v из U{ U Щ, одна из которых принадлежит Uj, а другая Щ, смежны. С другой стороны, в силу пункта (1) леммы 5.20 окрестность вершины v пересекает Uj и Uj. С учетом наблюдения, сделанного в начале пункта (3), имеем, что Uj U Uj разбивается на две компоненты связности, первая из которых содержится в [v], а другая ее не пересекает.
