О реберно регулярных графах, в которых каждая вершина лежит не более чем в одной хорошей паре

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если a, b — вершины графа Г, то через d(a, b) обозначается расстояние между а и b, а через r i (а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии i от вершины а. Подграф Г(а) = Г 1 (а) называется окрестностью вершины а и обозначается через [а], если граф Г фиксирован. Через а ^± обозначается подграф, являющийся шаром радиуса 1 с центром a.

Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г. Граф Г называется реберно регулярным графом с параметрами (v, к, А), если Г содержит v вершин, является регулярным степени к, и каждое ребро Г лежит в А треугольниках. Граф Г называется вполне регулярным графом с параметрами (v, к, А, ^), если Г реберно регулярен и подграф [а] П [b] содержит ^ вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Число вершин в [а] П [b] обозначим через А(а, b) (через ^(а, b)), если d(a, b) = 1 (если d(a, b) = 2), а соответствующий подграф назовем (^-) А-подграфом.

Пусть Г — реберно регулярный граф с параметрами (v, к, А) и b i = к — А — 1. Пара вершин u, w называется (почти) хорошей, если d(u, w) =2 и ^(u, w) равно к — 2b 1 + 1 (равно к — 2b i +2). Тройка вершин (u; w, z) называется (почти) хорошей, если w, z 6 ^(u) и ^(u, w) + ^(u, z) не больше 2к — 4b i + 3 (равно 2к — 4b i + 4).

Через K _{m 1 ,...,m n} обозначим полный n-дольный граф, с долями порядков m 1 , . . . , m _n . Если m i = ... = m n = m, то соответствующий граф обозначается через K _nxm . Если m >  2, то граф K i ,_m называется m-лапой. Треугольным графом T(m) называется граф с множеством неупорядоченных пар из X в качестве вершин, | X | = m и пары { а, b } , { c, d } смежны тогда и только тогда, когда они имеют единственный общий элемент. Граф на множестве вершин X х Y называется m х n-решеткой, если | X | = m, | Y | = n и вершины

( x i ,y i ) , (х 2 ,У 2 ) смежны тогда и только тогда, когда x i = Х 2 или y i = y ₂ . Граф Клебша (граф Шлефли) — это единственный сильно регулярный граф с параметрами (16, 10, 6, 6) (с параметрами (27, 16, 10, 8)). Для подграфа А через | А | обозначим число его вершин, а через X i (А) обозначим множество вершин из Г — А, смежных точно с i вершинами из А.

Если вершины u, w находятся на расстоянии i в Г, то через b i ( u, w) (через C i ( u, w)) обозначим число вершин в пересечении F i +1 (u) (пересечении F i_- 1 (u)) с [w]. Заметим, что в реберно регулярном графе с параметрами (v,k,А) значение b i (u, w ) не зависит от выбора ребра {u, w } и равно к — А — 1.

В [1, предложение и лемма 1.9] доказано, что если Г — связный реберно регулярный граф диаметра 2 с параметрами (v, к, А) и к = 3b 1 +Y, Y > — 2, то выполняются следующие утверждения:

• (1)    если Г содержит такую 3-коклику А, что любые ее две вершины образуют хорошие пары, то y 6 — 1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2;

• (2)    если некоторая вершина u графа Г лежит в хорошей паре, то либо y 6 b i — 6, либо b i = 1 и Г — многоугольник, либо b i =2 и Г — граф икосаэдра или граф с к = 4 диаметра, большего 2;

• (3)    если y >  0 и для некоторой вершины u подграф ^(u) содержит две вершины, образующие хорошие пары с u, то y < b i /2 — 2.

Уточнение утверждения (2) получено в [5]. В данной работе с помощью предложения о почти хороших тройках получено усиление утверждения (3).

Предложение 1. Пусть Г — связный реберно регулярный граф с параметрами (v, к, А), к = 3b i + y и y > 0. Если (u, w, z) — почти хорошая тройка и 6 = | [u] П [w] П [z] | , то выполняется одно из следующих утверждений:

• (1)    вершины w, z не смежны и 6 = 0;

• (2)    вершины w, z смежны и либо

• (i)    подграф [u] П [w] П [z] является 2 -кликой, y = 0, y(u, w) = y(u, z) = b i + 2, Г ₂ (u) П ([w] U [z]) = { w, z } U ([w] П [z]) и b _i >  8, либо

• (ii)    подграф [u] П [w] П [z] является 3 -кликой, y = 1, ^(u, w) = y(u, z) = b i +3, b _i = 3 и Г — граф Клебша, либо

• (iii)    подграф [u] П [w] П [z] является 4 -кликой, y = 1, ^(u, w) = y(u, z) = b i + 3, b i =5 и Г — граф Шлефли.

Теорема. Пусть Г — связный неполный реберно регулярный граф с параметрами (v, к, А) и к = 3b i + y , y >  0. Если y >  5b i /12 — 5, то каждая вершина графа Г лежит не более чем в одной хорошей паре.

Для конкретных параметров аналогичный результат можно получить при более слабых предположениях.

Предложение 2. Пусть Г — связный реберно регулярный граф с параметрами к = 17 и b i =6. Тогда v = 30, Г не содержит почти хороших пар, и каждая вершина графа Г лежит не более чем в одной хорошей паре.

• § 1.    Предварительные результаты

В этом параграфе приведены некоторые вспомогательные утверждения. Для вполне регулярного графа с параметрами (v, к, А, у) хорошо известно неравенство у >  к — 2b i +1 [2, теорема 1.2.3].

Лемма 1.1. Пусть Г — реберно регулярный граф с параметрами (v, k, X) и b i = к — X — 1. Если вершины u, w находятся на расстоянии 2 в Г, то выполняются следующие утверждения:

• (1)    степень любой вершины в ^-подграфе из Г не меньше к — 2b i ;

• (2)    вершина d имеет степень а в графе [u] П [w] тогда и только тогда, когда [d] содержит точно а — ( k — 2b i ) вершин вне u ^ U w ^ ;

• (3)    если ^(u, w ) = к — 2b i + 1, то подграф [u] П [w] является кликой и [d] С u ^ U w ^ для любой вершины d Е [u] П [w] ;

• (4)    если Г — (u ^ U w ^ ) содержит единственную вершину z, то ^(u, z) = ^(w, z).

C Пусть d Е [u] П [w]. Тогда | [d] — [u] | = | [d] — [w] | = b i . Поэтому по крайней мере k — 2 b i вершин из [d] содержится в [u] П [w]. Утверждение (1) доказано.

Пусть d Е [u] П [w] и степень d в этом ^-подграфе равна а. Тогда k = а + 2b i — | [d] — (u ^± U w ^± ) | . Поэтому [d] содержит а — (k — 2b _i ) вершин вне u ^± U w ^± . Утверждение (2) доказано.

Утверждение (3) следует из (1), (2).

Пусть { z } = Г — (u ^ U w ^ ). Так как число ребер между [u] — [w] и [w] — [u] равно b _i 1 [u] — [w] | — ^(u, z), то ^(u, z) = ^ ( w, z). B

Лемма 1.2. Пусть Г — связный реберно регулярный граф с параметрами (v, k, X), в котором b i =2. Тогда Г является одним из следующих графов:

• (1)    тривалентный граф без треугольников;

• (2)    реберный граф тривалентного графа без треугольников;

• (3)    полный многодольный граф К _гх з ;

• (4)    3 х 3 решетка, треугольный граф T(5) или граф Петерсена;

• (5)    граф икосаэдра.

C Это предложение 1 из [3]. B

Лемма 1.3. Пусть Г — связный реберно регулярный граф с параметрами (v, k, X), в котором b i = 3 . Тогда Г является одним из следующих графов:

• (1)    четырехвалентный граф без треугольников;

• (2)    реберный граф четырехвалентного графа без треугольников (в том числе 4 х 4 решетка ) ;

• (3)    локально шестиугольный граф (в том числе граф Пэли с параметрами (13, 6, 2, 3) и граф Шрикханде ) ;

• (4)    полный многодольный граф K _rX 4 ;

• (5)    треугольный граф T(6) или граф Клебша.

C Это предложение 2 из [3]. B

Пусть w,z Е ^(u). Пару вершин (u, w) назовем почти хорошей, если ^(u, w) = k — 2b i +2. Тройку вершин (u, w, z) назовем (почти) хорошей, если ^(u, w)+ ^(u, z) не больше 2k — 4b i + 3 (равно 2k — 4b i + 4). Свойства почти хороших троек вершин изучаются в следующих четырех леммах.

Лемма 1.4. Пусть Г — реберно регулярный граф с k >  3b i — 3, ^(u, w) + ^(u, z) = 2 k — 4b _i +4 для двух вершин w, z из Г 2 (u) , A = [u] П [w] П [z] и 6 = | A | . Тогда выполняется одно из утверждений:

• (1)    вершины w, z несмежны, 6 6 1 ив случае 6 = 1 имеем k = 3b i — 3;

• (2)    A содержит две несмежные вершины, 6 = 2 и k 6 3b i — 1;

• (3)    вершины w, z смежны, A является кликой и если 6 > 1, то либо

• (i)    подграф А содержит единственную вершину d, смежную с вершиной вне u ^ U [w] U [z], 5 6 2, к 6 3b _i — 2 и для e E A(d) подграф [d] U [e] содержит [w] П [z] — [u], а [d] П [e] содержится в { u, w, z } U ([u] П ([w] U [z])) U ([w] П [z] — [u]), либо

• ( ii )    подграф А не содержит вершин, смежных с вершиной вне u ^ U [w] U [z], и для любых двух вершин d, e E А подграф [d] П [e] содержит А — 1 + y вершин из {u,w,z} U ^{([ u ] П ([ w ] U [ z ])) U ([ w ] П [ z ] — [ u ])} , где y = | ^{[ w ] П [ z ] — ([ d ] U} [e]) | .

• <1    Все утверждения леммы, кроме оценок для к, следуют из леммы 1.7 [1].

Пусть вершины w, z смежны, и d — вершина из А, смежная с вершиной вне u ^ U [w] U [z]. Если 5 = 1, то | [u] П [d] | >  2(к — 2b i + 1) и к = 3b i — 3. Аналогичные рассуждения применимы к случаю, когда вершины w, z несмежны, и d E А.

Если 5 = 2, то | [u] П [d] | >  1 + 2(к — 2b _i ) и к 6 3 b _i — 2.

Пусть А содержит две несмежные вершины a, b. Тогда 5 = 2, | [u] П [d] | >  2(к — 2b i ) и к 6 3b _i — 1. B

Лемма 1.5. Пусть Г — реберно регулярный граф. Тогда

• (1)    если Г содержит хорошую тройку (u; w, z), то | [u] П [w] П [z] | < 2;

• (2)    если к = 3b i + y , Y >  0 и Г содержит хорошую пару { u, w } , то ^(u, z) >  b i + y + 3 для любой вершины z E [w] — [u], и b i >  8;

• (3)    если к >  3 b _i , b _i 6 6 и Г содержит почти хорошую пару { u, w } , то либо b _i = 1 и Г — граф K _nX 2 , n >  3, либо b i = 3 и Г — граф Клебша, либо b i =5 и Г — граф Шлефли.

• < Утверждение (1) следует из лемм 4, 5 [4].

Пусть z E [w] — [u]. Если ^(u, z) = b i + y + 1, то y = 0 и ввиду утверждения (1) подграф [u] П [w] П [z] содержит единственную вершину а и [a] П [u] содержит по b i + 7 вершин из [w] — [z] и из [z] — [w], противоречие с тем, что А = 2b _i + 7 — 1. Если ^(u, z) = b _i + y + 2, то по утверждению (1) имеем | [u] П [w] П [z] | 6 1, и [z] — w ^ содержит b i + 7 + 1 вершин из [u], противоречие. Значит, ^(u, z) >  b i + y + 3 для любой вершины z E [w] — [u].

Ввиду леммы 1.8 из [1], если к >  3b i и Г содержит хорошую пару u, w, то к 6 4b i — 6. В случае b i =6 имеем к = 18 и число ребер между [u] и [w] — [u] не больше 101. Так как 11 • 10 = 110, то Г = u ^± U w ^± и [w] — [u] содержит либо 9 вершин z с ^(u, z) = 9 и 2 вершины у с ^(u, z) = 10, либо 10 вершин z с ^(u, z) = 9 и 1 вершину у с ^(u, z) = 11.

Пусть ^(u, z) = 9, [u] П [w] П [z] = { a _i ,a ₂ ,a 3 } . Тогда [u] П [a i ] содержит 6 вершин из [u] П [w] и не менее 4 вершин из [u] П [z] — [w], [a i ] П [ a j ] содержит u, w, z, 5 вершин из [u] П [w], и не менее 2 вершин из [u] П [z] — [w]. Положим Q = { z E [w] — [u] | ^(u, z) =9 } . Тогда число ребер между [u] П [w] и Q не меньше 27, поэтому найдется вершина a E [u] П [w], смежная с 4 вершинами z i из Q. Без ограничения общности, вершины z i ,z 2 смежны. Противоречие с тем, что [z i ] П [z 2 ] содержит не менее 10 вершин из [u] П a ^ и не менее 8 вершин из w ^ — [u].

В случае b i = 7 имеем к = 22, А = 14 и v делится на 3. Отсюда v >  39, число ребер между [u] и Г ₂ (u) равно 7 • 22, но не меньше 9 + 13 • 11 + 19, противоречие. Утверждение (2) доказано.

Пусть к = 3b i + y , y >  0 и Г содержит почти хорошую пару (u, w). Заметим, что диаметр Г равен 2, и если Г — сильно регулярный граф, то он имеет собственное значение — 2.

Если b i = 1, то Г — многоугольник или граф K _nX 2 . В первом случае к = 2b i , а во втором каждая пара несмежных вершин является почти хорошей и n >  3.

Если b i = 2, то ввиду леммы 1.3 Г — 3 х 3 решетка, треугольный граф T(5) или граф Петерсена. В любом случае к < 3b i .

Если b _i = 3, то ввиду леммы 1.4 Г — граф Клебша.

Если b i = 4 и к >  10, то по предложению 3 из [3] Г является полным многодольным графом K r x 5 или треугольным графом T (7). В первом случае — 2 не является собственным значением Г, а во втором k <  3b i .

Если b i =5 и к >  15, то по теореме из [6] Г является полным многодольным графом K r x 6 или графом Шлефли. Но в первом случае — 2 не является собственным значением Г.

Пусть b i =6 и к >  18. Если граф Г сильно регулярен, то он имеет собственное значение — 2 и к <  3b i . Поэтому граф Г не является сильно регулярным и | u ^ U w ^ | = 30 + y .

Допустим, что ^(u, z) = 8 + y для смежной с w вершины z из ^(u). Положим А = [u] П [w] П [z] и 5 = | А | . Если 5 6 2, то y = 0, Г ₂ (u) С {w,z} U ([w] П [z]) и | Г ₂ (u) | = 11. Далее, число ребер между [u] и ^(u) — { w, z} равно 92. Положим [w] П [z] = { a, b } , S i = [a] — ([u] U { w,z } ), S ₂ = [b] — ([u] U { w,z } ). Пусть c E S i . Если c ^ содержит S i , то степень a в графе [u] П [c] равна 6, [u] П [c] содержит по 3 вершины из [u] П [w] — [z], [u] П [z] — [w] и из [u] — ([w] U [z]), поэтому ^(u, c) = 10. Если же c ^± не содержит S _i , то степень a в графе [u] П [c] равна 8, [u] П [c] содержит по 4 вершины из [u] П [w] — [z], [u] П [z] — [w] и 2 вершины из [u] — ([w] U [z]), поэтому ^(u, c) = 11. В последнем случае подграф S i является 3-лапой или объединением двух изолированных ребер, а S 2 является 4-кликой. Если S i является 3-лапой, то число ребер между ^(u) — { w, z } и [u] — ([w] U [z]) не больше 23, противоречие с тем, что каждая из четырех вершин в [u] — ([w] U [z]) смежна с 6 вершинами из Г 2 (u) — { w, z } . Если S i является объединением двух изолированных ребер, то для вершины e из ^(u) — (a ^ U b ^ ) имеем ^(u, e) = 8, поэтому [e] содержит S i и S 2 . Далее, [c] содержит 3 вершины из S 2 для любой вершины c E S i , противоречие с тем, что для d E S 2 подграф [d] содержит 2 вершины из S i .

Итак, S i , S 2 являются кликами и ^(u, e) = 12 и [e] содержит [u] П [w] — [z], [u] П [z] — [w] и 4 вершины из S i U S 2 . Поэтому ^(a, e) + +(b, e) =28 и число ребер между [e] и Г 2 (e) — { u, a, b } равно 60, противоречие.

Пусть 5 >  3. Ввиду леммы 1.6 граф А является кликой. Положим S = [w] П [z] — [u].

Покажем, что 5 >  7 + 4. В противном случае | S | > 7, для любой вершины a i из А имеем | S — [a i ] | > 3 и для двух вершин a i , a 2 из А — { a i } подграф [a i ] П [a 2 ] содержит более 6 + y вершин из [u] П ([w] U [z]) и менее 2 вершин из S, противоречие. Так как |^(u) | > 9 + 5 — y , то число ребер между [u] и ^(u) равно 6(18 + y ), но не меньше 13(8 + y ). Отсюда 7y 6 4, 7 = 0, 5 = 4 и | Г ₂ (u) | = 13.

Положим А = { a i ,..., a 4 } . Тогда [a i ] П [a j ] содержит не менее 9 вершин из [u] П ([w] U [z]) и не более 2 вершин из S.

Допустим, что [a i ] содержит не более 3 вершин из S. Тогда | S — [a i ] | >  4, поэтому [a i ] содержит точно 3 вершины из S. Если [a 2 ] содержит 3 вершины из S, то [a 3 ] П [a 4 ] содержит не менее 3 вершин из S, противоречие. Значит, [a i ] содержит b _i — 2 вершин из S для любой вершины a i E А — { a i } . Теперь число ребер между А и [u] — ([w] U [z]) не меньше 7 и некоторая вершина из [u] — ([w] U [z]) смежна с 2 вершинами a i , a j . Ясно, что | [a i ] П S | = | [a j ] П S | =4. Если | [a i ] П S | = 3, то [a i ] П [a i ] или [a i ] П [a j ] содержит не менее 2 вершин из S, противоречие. Значит, | [a] П S | = 4 для любой вершины a E А и [a l ] содержит по 2 вершины из S — [a i ] и из S — [a j ]. Далее, [u] — ([w] U [z]) содержит вторую вершину, смежную с 2 вершинами из А, противоречие.

Пусть ^(u, z) > 8 + y для любой смежной с w вершины z из ^(u). В случае v = 30 + 7 подграф [u] П [w] является полным многодольным с долями порядка 2, поэтому y четно. В этом случае вершина из Г2(u) — {w} смежна в среднем с 10 + y/2 вершинами из [u] и 8 + y 6 10 + y/2. Если y = 4, то граф Г является сильно регулярным, противоречие. Значит, y E {0, 2}. Если 7 = 2, то ^(u, z) = 11 для любой вершины z E [w] — [u], и подграфы [u] П [w], [w] — [u] изоморфны K5X2. В этом случае для любой вершины x подграф ^(x) содержит точно 10 вершин у с y(x,у) = 11, поэтому x лежит в пяти 3-кокликах и число 3-коклик в Г равно 32 • 5/3, противоречие.

Пусть y = 0. Если у (u, z) = 9 для некоторой вершины z Е [w] — [u], то Г — (u ^ U z ^ ) содержит единственную вершину у и по лемме 1.1 имеем ^(u, у) = у(у, z). Поэтому [у] содержит в вершин из [u] П [z] и ^(u, у) = (18+в)/2. Если в = 0, то [w] С у ^ U z ^ и степень w в графе [у] П [z] равна 8, противоречие. Если в = 2, то для вершины а Е [u] П [у] П [z] подграф [а] — у ^ содержит u, z и не менее 6 вершин из [u] П [z] — [у], противоречие. Если в = 4, то для вершины а Е [u] П [у] П [z] подграф [а] — у ^ содержит u, z и 4 вершины из [u] П [z] — [у], поэтому [u] П [у] П [z] является кликой, и подграф [у] содержит [а] П ([u] — [z]) и [а] П ([z] — [u]). Положим [u] П [у] П [z] = { а 1 ,..., а ₄ } . Тогда [а 1 ] П [а ₂ ] содержит u, у, z, не менее 5 вершин из [u] П [z] и не более 3 вершин из ([u] — [z]) U ([z] — [u]). Без ограничения общности можно считать, что [а 1 ] П [а 2 ] содержит 1 вершину из [u] — [z] и 2 вершины из [z] — [u]. Тогда [а з ] П ([u] — [z]) содержит по 2 вершины из [а 1 ] — [а 2 ] и из [а 2 ] — [а 1 ]. Противоречие с тем, что [а з ] П ([z] — [u]) содержит 2 вершины из [а 1 ] — [а 2 ] или из [а 2 ] — [а 1 ].

Если в = 8, то ^(u, у) = у (у, z) = 13, число ребер между [у] и Г ₂ (у) — { u, z } равно 82 и ^ ( x i , у) = 9 для по крайней мере 6 вершин x i из Г 2 (у). Далее, [u] — [z] или [z] — [u], для определенности, [u] — [z] содержит не менее 3 таких вершин x i . Противоречие с тем, что число ребер между [u] и ^( u) — { у, x i , x 2 , x 3 } равно 108 — 13 — 3 • 12 = 59.

Значит, в = 6, ^(u, у) = ^(у, z) = 12, число ребер между [у] и Г ₂ (у) — { u, z } равно 84 и y(x i , у) = 9 для по крайней мере 4 вершин x i из Г 2 (у). Заметим, что ^(у, b) = 12 для не более чем одной вершины b Е Г 2 (у) — { u, z } . Если ^(у, b) = 12, то либо у (у, с) = 9 для любой вершины с Е Г ₂ (у) — { b, u, z } , либо ^(у, а) = 8, ^(у, d) = 10 и ^(у, C j ) = 9 для 6 вершин C j Е Г 2 (у). Заметим, что в случае у (у, с) = 9 для с Е [z] — [u] имеем у (u, с) = 12, поэтому каждый из подграфов [u] П [z], [u] — [z] и [z] — [u] содержит по 2 вершины C j такие, что ^(у, C j ) = 9. Противоречие с тем, что тогда | Г 2 (у) — b ^ | 6 3. Итак, ^(у, b) < 12 для любой вершины b Е Г 2 (у) — { u, z } . Если [u] — [z] содержит такую вершину х, что ^(у, x) = 9, то ^(х, z) = 12. Поэтому ^(у, а) = 8 для единственной вершины а Е Г 2 (у) и { x | у(у, x) = 9 } содержит вершину x i из [u] — [z], X 2 из [z] — [u] и 2 вершины х з ,х 4 из [u] П [z]. Противоречие с тем, что ^(у, е) = 12 для е Е Г — (x ^ U у ^ ).

Таким образом, для любой вершины u найдется единственная вершина w с у (u, w) = 8 и у (u, z) = 10 для любой вершины z Е Г ₂ (u) — { w } . Положим Г — (u ^± U z ^± ) = { x, у } . Если вершины x,y не смежны, то [x] содержит по 7 вершин из [u] — [z], [z] — [u] и 4 вершины из [u] П [z] Если вершины x, у смежны, то [x] содержит по 6 вершин из [u] — [z], [z] — [u] и 5 вершин из [u] П [z]. В любом случае имеем противоречие с тем, что ^(u, x) = 11.

В случае v >  31 + y число ребер между [u] и ^(u) равно 6(18 + y) , но не меньше 2(8 + y) + 10(9 + y ), поэтому 6y 6 2 и y = 0. Далее, v = 31 и Г — (u ^ U w ^ ) содержит единственную вершину z. По лемме 1.1 имеем ^(u, z) = y(w, z), поэтому [z] содержит в вершин из [u] П [w] и ^(u, z) = 9 + в/2. Если а Е [u] П [w] П [z], то [а] — z ^± содержит u, w и 8 — в вершин из [u] П [w], поэтому в >  4. В случае в = 4 для любых двух вершин а 1 ,а ₂ Е [u] П [w] П [z] подграф [а 1 ] П [а ₂ ] содержит u, w, z, 6 вершин из [u] П [w] и по одной вершине из ([u] — [w]) П [z] и из ([w] — [u]) П [z]. Противоречие с тем, что для а з Е [u] П [w] П [z] — { а 1 , а ₂ } подграф [а 1 ] П [а з ] содержит u, w, z, 6 вершин из [u] П [w] и по 3 вершины из ([u] — [w]) П [z] и из ([w] — [u]) П [z]. Итак, если в > 0, то в >  6 и число ребер между [z] и ^( z) — { u, w } равно 84, противоречие.

Отсюда в = 0, [u] П [w] — полный 4-дольный граф с долями порядка 2 и у (u, z) = ^(w, z) = 9. Итак, для любой вершины x либо ^(x, у) = 9 для любой вершины у Е ^(x), либо Г2(x) содержит такие вершины а, b, что ^(а, x) = 8, y(b, x) = 10 и ^(x, у) = 9 для любой вершины y Е Г2(х)—{a, b}. Пусть e —вершина из [w] — ([u]U[z]). Тогда [e] содержит не менее 5 вершин из [u] П [z], не более 4 вершин из [u] П [w] и не менее 7 вершин из [w] П [z]. Противоречие с тем, что ^(e, у) > 12. B

Лемма 1.6. Пусть Г — реберно регулярный граф с параметрами (v, к, A), bi = 7, к = 21 + y и Y >  0- Тогда Y нечетно, и Г не содержит почти хороших пар.

• <1 Пусть b i = 7, к = 21 + y , Y >  0 и Г содержит почти хорошую пару (u, w). Заметим, что диаметр Г равен 2, и если Г — сильно регулярный граф, то он является графом в половинном случае или имеет собственное значение — 2. В первом случае ^ = b i = к — 2b i + 2. В случае n х n-решетки имеем b i = n — 1 и n = 8. В случае треугольного графа T(m) имеем b i = m — 3 и m = 10. В любом случае к < 3b i . Значит, Г не является сильно регулярным графом и | u ^ U w ^ | = 35 + 7.

Допустим, что ^(u, z) = 9 + y для смежной с w вершины z из ^(u). Положим А = [u] П [w] П [z] и 5 = | А | . Если 5 6 2, то y = 0, к = 21, A = 13, противоречие с тем, что кА четно.

Пусть 5 >  3. Ввиду леммы 1.4 граф А является кликой. Положим X = [w] П [z] — [u]. Тогда | X | = 13 + y — 5. Для двух вершин a i , a 2 из А подграф [a i ] П [a 2 ] содержит u, w, z, не менее 14 + 2y — 5 вершин из [u] П ([w] U [z]) и не более 5 — y — 4 вершин из X.

Покажем, что 5 >  y + 5. В противном случае 5 6 y + 4, | X | >  9, для любой вершины a i из А имеем | X — [a i ] | >  4 и для двух вершин a i , a 2 из А — { a i } подграф [a i ] П [a 2 ] содержит не менее 2 вершин из X — [a i ], противоречие. Так как | Г 2 (u) | >  11 + 5 — y , то число ребер между [u] и ^(u) равно 7(21 + y) , но не меньше 16(9 + y )• Отсюда 9y 6 3, y = 0, к = 21, А = 13, противоречие с тем, что кА четно.

Итак, ^(u, z) >  9+y для любой смежной с w вершины z из [w] — [u]. Теперь число ребер между [u] и ^(u) равно 7(21 + y ), но не меньше 13(10 + y) — 1. Отсюда 6y 6 18. В случае y = 3 имеем v = 38, к = 24, А = 16, подграф [u] П [w] является полным многодольным с долями порядка 2, и каждая вершина из Г ₂ (u) — { w } смежна с 13 вершинами из [u]. Пусть z Е Г ₂ (u) — { w } , Г — (u ^± U z ^± ) = { у } . По лемме 1.1 имеем ^(u, у) = ^(u, z) = 13. Поэтому [у] содержит 2 вершины из [u] П [z] и по 10 вершин из [u] — [z] и из [z] — [u]. Для вершины a Е [u] П [z] П [у] степень a в графе [u] П [z] равна 11. Противоречие с тем, что [a] — у ^ содержит u, z и не менее 10 вершин из [u] П [z].

Значит, y = 1, к = 22, А = 14 и v делится на 3. Если v >  39, то число ребер между [u] и ^(u) равно 7 • 22, но не меньше 16 • 11, противоречие. Итак, v = 36 и Г = u ^ U w ^ .

Пусть ^(u, z) = 11, Г — (u ^ U z ^ ) = { у } и [у] содержит 1 вершин из [u] П [z]. По лемме 1.1 имеем ^(u,у) = ^(u, z) = 11 + 1/2. Если 1 = 0, то [у] = ([u] — [z]) U ([z] — [u]). Поэтому [w] содержит по 6 вершин из [u] П [z] и из [u] — [z], противоречие. Для вершины a Е [u] П [z] П [у] степень a в графе [u] П [z] равна 9. Если 0 <1 6 4, то [a] — у ^ содержит u, z и 6 вершин из [u] П [w], противоречие. Если 1 = 6, то [a] — у ^± содержит u, z, не менее 4 вершин из [u] П [z] и не более 1 вершины из ([u] — [z]) U ([z] — [u]). Поэтому [a] содержит 9 вершин из 16-вершинного подграфа Ф = ([u] П [у] — [w]) U ([w] П [у] — [u]). Для попарно смежных вершин a, c, e Е [u] П [z] П [у] подграф [a] П [c] содержит u, w, у, не менее 6 вершин из [u] П [w] и не более 5 вершин из Ф, и [e] содержит по 3 вершины из Ф — [a] и из Ф — [c]. Отсюда подграф [u] П [z] П [у] является кликой и для подходящей вершины f Е [u] П [z] П [у] — { e } подграф [e] П [f] содержит 3 вершины из Ф — ([a] U [c]) и еще одну вершину из Ф, противоречие.

Если 1 = 10, то ^(u, у) = ^(u, z) = 16, число ребер между [у] и Г2(у) — {u, z} равно 122, поэтому найдется по крайней мере 8 вершин ei из Г2(у) — {u, z} с ^(у, ei) = 11. Без ограничения общности, 4 из этих вершин попадают в [z] — [u]. Для ei Е [z] — [у] имеем Г — (e4 U у±) = {u} и по лемме 1.1 имеем ^(u, e) = 16. Противоречие с тем, что число ребер между [у] и Г2(u) — ({w, y, z} U {ei}) равно 53. Если l = 8, то ^(u, у) = ^(u, z) = 15, число ребер между [у] и Г2(у) — {u, z} равно 124, поэтому найдется по крайней мере 6 вершин ei из Г2(у) — {u, z} с ^(у, ei) = 11. Если 3 из этих вершин попадают в [z] — [u] или в [u] — [z], то мы получим противоречие как и выше. Значит, {ei} содержит по 2 вершины из [u] П [z], [z] — [u], [u] — [z] и число ребер между [у] и X = Г2(u) — ({w, у, z} U {ei}) равно 88. Поэтому [u] — ([у] U [z]) и [z] — ([у] U [u]) содержат по 2 вершины xj с ^(x,у) = 15. Противоречие с тем, что число ребер между [у] и Г2(у) — ({u, z} U {xj}) равно 64.

Итак, P ₂ (u) не содержит вершин z с ^ ( u, z) = 11. Поэтому ^(u, у) = 12 для любой вершины у Е r ₂ (u) — { w } . Положим Г — (u ^ U у ^ ) = {z, z ⁰ } . Если вершины z, z ⁰ смежны, то [z] содержит 3 вершины из [u] П [z] и по 9 вершин из [u] — [у], [у] — [u]. Если же вершины z, z ⁰ не смежны, то [z] содержит 2 вершины из [u] П [z] и по 10 вершин из [u] — [у], [у] — [u]. В любом случае для вершины а из [u] П [у] П [z] подграф [a] — z ^ содержит u, у и не менее 7 вершин из [u] П [z], противоречие. B

• § 2.    Почти хорошие тройки в графах с k > 3bi

В этом параграфе Г является связным реберно регулярным графом с k = 3b i + y , Y >  0. Пусть b _i 6 5. Тогда Г не содержит хороших пар, а если Г содержит почти хорошую пару, то по лемме 1.5 граф Г является графом Клебша или графом Шлефли и выполняется заключение предложения 1.

Лемма 2.1. Пусть b i > 5, ^(u, w) + ^(u, z) 6 2b i + 2y + 4 для смежных вершин w, z из Г ₂ (u), А = [u] П [w] П [z] и 5 = | А | . Тогда подграф А является кликой и либо y = 0, ^(u, w) = ^(u, z) = b i +2, 5 = 2, b i >  8 и | Г 2 (u) | = 2b i — 1, либо выполняются следующие утверждения:

• (1)    5 >  b i /2 + y + 2;

• (2)    если ^(u, w) = ^(u, z) = b i + y + 2, то для любой вершины у из [z] — (w ^ U [u]) имеем ^(u, у) >  b _i + Y + 3, а для любой вершины x из [w] П [z] — [u] имеем ^(u, x) >  b _i + y + 2;

• (3)    если ^(u, w) = b _i + y + 1, ^(u, z) = b _i + y + 3, то для любой вершины у из [z] — (w ^ U [u]) имеем ^(u, у) >  b i + y + 2, а для любой вершины x из [w] — [u] имеем ^(u, x) >  b i + Y + 3.

• <1    Если 5 6 2, то [z] — w ^ или [w] — z ^ содержит не менее b i вершин из [u], поэтому Y = 0, ^(u, w) = ^(u, z) = b i +2 и 5 = 2. Если А содержит две несмежные вершины a, c, то [а] П [u] содержит по b i вершин из [w] и из [z], противоречие с тем, что А = 2b i — 1. Значит, А является 2-кликой и ^(u, w) = ^(u, z) = b i +2. Так как [w] — z ^ содержит b i вершин из [u], то ^(u) П ([w] U [z]) = { w, z } U ([w] П [z]). Ввиду лемм 1.5, 1.6 имеем b i >  8 и выполняется заключение леммы.

Пусть 3 6 5 < b _i /2 + y + 2. Ввиду леммы 1.4 граф А является кликой. Положим X = [w] П [z] — [u]. Тогда | X | = А — 5 > 3b _i /2 — 3 и для двух вершин a _i , a ₂ из А подграф [a _i ] П [a ₂ ] содержит u, w, z, 5 — 2 вершин из А, не менее 2b _i +2y — 25 вершин из ([u] — А) П ([w] U [z]) и не более 5 — y — 2 вершин из X. Докажем сначала утверждение

• (а)    5 >  b i /2 + y + 1.

В противном случае | X | > 3b i /2 — 2, для любой вершины a i из А имеем | X — [a i ] | > b i /2 и для двух вершин a i , a 2 из А — { a i } подграф [a i ] П [a 2 ] содержит более 3b i /2 + y — 3 вершин из [u] П ([w] U [z]) и менее b i /2 — 1 вершин из X. Отсюда b i = 2t + 1, | X — [a i ] | = t + 1 и для двух вершин a i , a 2 из А — { a i } подграф [a i ] П [a 2 ] содержит t — 1 вершин из X — [a i ]. Отсюда | X — [a i ] | = t + 1, | [a i ] П X | = 2t — 1 и 5 = t + 1 + y • Если 5 > 3, то [a ₄ ] П X содержит единственную вершину из [a i ] П X и t — 1 = 1, противоречие. Если 5 = 3, то y = 0 и снова t = 2, противоречие с леммой 1.5. Утверждение (a) доказано.

Предположим, что b i = 2t и 6 = t + 7 + 1. Тогда | X | = 3t — 2 и [a i ] П [a 2 ] содержит u, w, z, не менее 3t + y — 3 вершин из [u] П ([w] U [z]) и не более t — 1 вершин из X. Докажем утверждение

• (b)    каждая вершина из А смежна с b i — 2 вершинами из X.

Допустим, что [a i ] содержит не более b i — 3 вершин из X. Тогда | X — [a i ] | >  t + 1, поэтому [a i ] содержит точно b i — 3 вершин из X. Если [a 2 ] содержит b i — 3 вершин из X, то [a s ] П [a 4 ] содержит не менее 2t — 3 вершин из X и 2t — 3 6 t — 1, противоречие. Значит, [a i ] содержит b i — 2 вершин из X для любой вершины a i Е А — { a i } . Поэтому [a 2 ] U [a s ] содержит 2t — 4 вершин из [a i ] П X, [a 4 ] П X содержит единственную вершину из [a i ] П X и t — 2 = 1. Противоречие с леммой 1.5. Докажем утверждение

• (c)    каждая вершина из X смежна не менее чем с t + 7 — 1 вершинами из А.

Предположим, что 3 вершины a i , a 2 , a s из А не смежны с вершиной у из X. Ввиду леммы 1.6 для любых различных i,j Е { 1, 2, 3 } подграф [a i ] U [ a j ] содержит X — { у } . Поэтому X — { у } содержит по t — 1 вершин из X — [a i ] для i = 1, 2, 3. Для a 4 Е А — { a i , a 2 , a s } подграф [a 4 ] содержит у и не менее 3(t — 2) вершин из X — { у } . Отсюда t 6 3, противоречие с леммой 1.5. Докажем утверждение

• (d)    X не содержится в [a i ] U [a 2 ] для любых a i , a 2 Е А.

Пусть X С [a _i ] U [a ₂ ]. Тогда X содержит t — 2 вершин из [a _i ] П [a ₂ ] и по t вершин из [a _i ] — [a ₂ ], [a ₂ ] — [a _i ]. Далее, X П [a s ] содержит по b _i /2 — 1 вершин из [a _i ] — [a ₂ ], [a ₂ ] — [a _i ] и не пересекает [a i ] П [a 2 ]. Но в этом случае вершина из X П [a i ] П [a 2 ] не смежна ни с одной вершиной из А — { a i , a 2 } , и по утверждению (c) имеем t = 3. Противоречие с леммой 1.5. Утверждение (d) доказано.

Число пар вершин в А равно (t ⁺Y⁺ⁱ) . Из утверждений (c, d) следует, что ( ^{t +}Y⁺ⁱ) = 3b i /2 — 2. Отсюда y = 0 и b i =8. Противоречие с тем, что некоторая вершина из [u] П [z] — [w] не смежна с парой вершин a i , a j из А и [a i ] П [a j ] содержит u, w, z, 10 вершин из [u] П ([w] U [z]) и 3 вершины из X.

Предположим теперь, что b i = 2t + 1 и 6 = t + 7 + 2. Тогда | X | = 3t — 1 и [a i ] П [a 2 ] содержит u, w, z, не менее 3t + y — 2 вершин из [u] П ([w] U [z]) и не более t вершин из X. Докажем утверждение

• (e)    если вершина a i из А смежна менее чем с b i — 2 вершинами из X, то | X П [a i ] | = b i — 3 и [a i ] содержит b i — 2 вершин из X для любой вершины a i Е А — { a i } .

Допустим, что [a _i ] содержит b _i — 4 = 2t — 3 вершин из X. Тогда | X — [a _i ] | = t + 2, поэтому [a i ] содержит b i — 2 вершин из X для любой вершины a i Е А — { a i } . Поэтому [a 2 ] П [a s ] содержит 2t — 4 вершин из [a i ] П X, [a 4 ] П X содержит единственную вершину из [a i ] П X и t — 2 = 1. Противоречие с леммой 1.6.

Допустим, что [a _i ] содержит b _i — 3 = 2t — 2 вершин из X. Тогда | X — [a _i ] | = t + 1. Если [a 2 ] содержит b i — 3 вершин из X, то [a s ] П [a 4 ] содержит не менее 2t — 3 вершин из X и 2t — 3 6 t. Противоречие с леммой 1.6. Значит, [a i ] содержит b i — 2 вершин из X для любой вершины a i Е А — { a i } . Докажем утверждение

• (f)    каждая вершина из X смежна не менее чем с t + 7 вершинами из А.

Предположим, что 3 вершины a i ,a j , a i из А не смежны с вершиной у из X. Ввиду леммы 1.4 объединение окрестностей любых двух вершин из { a i , a j , a i } содержит X — { у } . Поэтому X — { у } содержит по t — 1 вершин из X — [a i ], X — [a j- ] и t вершин из X — [a i ]. Для a Е А — { a i , a j , a i } подграф [a] содержит у и не менее 3t — 5 вершин из X — { у } . Отсюда t 6 3, противоречие с леммой 1.6. Утверждение (f) доказано.

Теперь число ребер между X и А не больше (t+Y+2)(2t — 1), но не меньше (3t — 1)(t+Y). Поэтому t ² + tY 6 4t — 2, противоречие с тем, что t >  4.

Итак, 6 >  b _i /2 + y + 2. Так как b _i >  8, то 6 >  6 + y . Утверждение (1) доказано.

Если ^(u, w) = ^(u, z ) = b i + Y + 2, то для любой вершины у из [z] — (w ^ U [u]) имеем ^(u, y ) > b i + y + 3. Иначе [u] П [у] не пересекает [w] и содержит не более b i /2 вершин из [z] — [w], противоречие. Утверждение (2) доказано.

Пусть ^(u, w) = b i + y + 1, ^(u, z) = b i + Y + 3. Тогда для любой вершины у из [z] — (w ^ U [u]) имеем ^(u, у) >  b i + y + 2. Иначе [u] П [у] содержит не более b i /2 вершин из [z]. А для любой вершины x из [w] — [u] ввиду леммы 1.5 имеем ^(u, x) >  b i + y + 3. B

Лемма 2.2. Пусть выполнены условия леммы 2.1, 6 >  2 и X = [w] П [z] — [u]. Тогда каждая вершина из А смежна по крайней мере с 6 — y — 4 вершинами из [u] — ([w] U [z]) и выполняются следующие утверждения:

• (1)    если y = 0, то b i >  12;

• (2)    каждая вершина из [u] — ([w] U [z]) смежна не более чем с 3 вершинами из А ;

• (3)    6 < b 1 + y — 3 и b _i >  11;

• (4)    некоторая вершина из [u] — ([w] U [z]) смежна с 3 вершинами из А.

• <1    Пусть 6 > 2, a £ А. Тогда [a] П [u] содержит не более 2b i + 2y + 3 — 6 вершин из [w] U [z] и не менее 6 — y — 4 вершин из [u] — ([w] U [z]).

Пусть y = 0. Тогда 6 >  b _i /2+2, k = 3b i , A = 2b _i — 1 и b _i четно. Если ^(u, w) = ^(u, z) = b _i + 2, то число ребер между [u] и r ₂ (u) не меньше (26 — 4)(b _i + 3) + (2b _i + 1 — 6)(b _i +2). Поэтому 6(b _i +4) 6 b i — b _i +10 и b _i /2 >  7 — 30/(b _i +4). Если ^(u, w) = b _i + 1, ^(u, z) = b _i +3, то число ребер между [u] и Г ₂ (u) не меньше (6 — 1)(b i + 2) + (2b i — 3)(b i + 3). Поэтому 6(b i + 2) 6 b i — 2b i + 11 и b i /2 >  6 — 19/(b i +2). В любом случае b i >  10.

Пусть b i = 10. Тогда k = 30, A = 19, | X | = 12 и 6 =7. Заметим, что каждая вершина из X смежна не менее чем с 4 вершинами из А. Так как число ребер между А и X не больше 56, то X содержит 4 вершины у 1 , ... ,у 4 , смежные с четверками вершин из А. Пусть вершина у 1 не смежна с вершинами a i ,..., а з из А. Тогда [a i ] П [a j ] не пересекает [u] — ([w] U [z]) и X — [a i ] не пересекает X — [a j ] для различных i,j G { 1, 2, 3 } . Поэтому можно считать, что | X — [a 1 ] | = | X — [a ₂ ] | =5 и | X — [« з ] | = 4. Отсюда подграф [u] — ([w] U [z]) разбивается его пересечениями с [a i ]. Противоречие с тем, что для подходящих a G А — { a i ,..., « з } и i G { 1, 2, 3 } подграф [a] П [a i ] содержит 2 вершины из [u] — ([w] U [z]). Утверждение (1) доказано.

Пусть e — вершина из [u] — ([w] U [z]), смежная с 4 вершинами a i ,..., a ₄ из А. Тогда | X — [a i ] | >  b i + 1 + Y — 6, [a 4 ] содержит не меньше 3(b i + 1 + Y — 6) вершин из (X — [a i ]) U (X — [a ₂ ]) U (X — [« з ]) и 3(b 1 + 1 + Y — 6) 6 b i — 2. Поэтому 6 >  (2b 1 + 5)/3 + Y-

Так как 4(6 — y — 5) 6 b 1 + 6 — y — 5, то (2b 1 + 5)/3 + y 6 6 6 b 1 /3 + y + 5 и b 1 6 9.

Пусть b i = 8. Тогда 6 = 7 + y , k = 24 + y , A = 15 + y • Далее, каждая вершина a i смежна с 6 вершинами из X и число ребер между [u] — ([w] U [z] U{ e } ) и { a i ,..., a 4 } равно 16. Противоречие с тем, что | [u] — ([w] U [z] U { e } ) | = 10.

Пусть b 1 = 9. Тогда 6 = 8 + y , k = 27 + y , A = 17 + Y- Далее, либо каждая вершина a i смежна с 7 вершинами из X, либо одна вершина a i смежна с 6 вершинами из X, а остальные с 7. Поэтому число ребер между [u] — ([w] U [z] U { e } ) и { a 1 ,..., a ₄ } не меньше 19. Противоречие с тем, что | [u] — ([w] U [z] U { e } ) | = 12. Утверждение (2) доказано.

Пусть 6 >  b i + y — 3. Если ^(u, w) = ^(u, z) = b i +2, то число ребер между [u] и r ₂ (u) не меньше (2b 1 — 10)(b 1 + y + 3) + (b 1 + 4)(b 1 + y + 2). Поэтому 2b 1 Y + 2b 1 6 6y + 22, Y = 0 и b i 6 11. Противоречие с утверждением (1). Если ^(u, w) = b i + 1, ^(u, z) = b i +3, то число ребер между [u] и r ₂ (u) не меньше (b i — 4)(b i + y + 2) + (2b i — 2)(b i + y + 3). Поэтому 2b i y + 2b i 6 6y + 14, противоречие.

Итак, b 1 /2 + y + 2 < b 1 + y — 3 и b 1 > 10. Утверждение (3) доказано.

Если каждая вершина из [u] — ([w] U [z]) смежна не более чем с 2 вершинами из А, то 2(b1 + 6 — y — 4) > 6(6 — y — 4). Поэтому 2(b1 — y — 4) > 6(6 — y — 6) > (b1/2 + y + 2)(b1/2 — 4) и bl + bi(2Y - 12) — 8y + 8 6 0. В случае y = 0 имеем bi 6 11, противоречие с утверждением (1). Если 1 6 Y 6 5, то bi 6 10, противоречие с утверждением (3). В случае y > 6 имеем bi(bi + y) — 12bi + biY — 8y + 8 > 0, противоречие. B

Лемма 2.3. Пусть выполнены условия леммы 2.1, 6 > 2 и вершина e из [u] — ([w] U [z]) смежна с тремя вершинами a i , а 2 , а з из А. Тогда выполняются следующие утверждения:

• (1)    6 >  (2b i + 2)/3 + Y и b i >  14;

• (2)    Y = 0, b _i = 14 и 6 = 10.

<1 Заметим, что | X — [a i ] | >  b i + Y + 1 — 6, поэтому для любой вершины а £ А — [e] подграф [а] содержит по b _i +Y —6 вершин из X — [a i ], 3(b _i +Y - 6) 6 b _i — 2 и 6 >  (2b _i +2)/3+Y.

Теперь (2b i + 2)/3 + y 6 6 < b i + y — 3 и b i >  14. Утверждение (1) доказано.

Так как каждая вершина из [u] — ([w] U [z]) смежна не более чем с 3 вершинами из А, то 3(b i + 6 — y — 4) >  6(6 — y — 4). Поэтому 3(b i — y — 4) >  6(6 — y — 7) >  ((2b i + 2)/3 + Y)((2b i + 2)/3 — 7) и 4b i + 6^y — 61b i — 30y + 70 6 0.

В случае y = 0 имеем 4b i — 61b i + 70 6 0 и b i 6 14. В случае y = 1 имеем b i 6 12. В случае y = 2 имеем 4b i — 49b i + 10 6 0 и b i 6 12. В случае y = 3 имеем b i 6 11. В случаях 4 6 y 6 5 имеем b i 6 10. Наконец, если y >  6, то (4b i +3b i Y — 61b i ) + (3b i Y — 30y)+70 > 0, противоречие. B

Завершим доказательство предложения 1. Имеем y = 0, b i = 14, k = 42, А = 27 и 6 = 10. Но в этом случае 4b i — 61b _i + 70 = 0, поэтому каждая вершина из [u] — ([w] U [z]) смежна точно с 3 вершинами из А, и каждая вершина из А смежна точно с 6 — y — 4 = 6 вершинами из [u] — ([w] U [z]). Отсюда каждая вершина из А смежна точно с 10 вершинами из X.

Пусть вершина e из [u] — ([w] U [z]) смежна с тремя вершинами a i , а 2 , а з из А. Тогда | X — [a i ] | = 7 и X П [а з ] содержит по 7 вершин из X — [a i ] и из X — [а 2 ], противоречие. B

• § 3.    Реберно регулярный граф с k = 17, bi = 6

В этом параграфе Г является связным реберно регулярным графом с k = 17, b i = 6. По следствию из [7] Г является графом диаметра 2 с не более чем 2k вершинами. Так как А = 10, число vk четно и vkA делится на 6, то v = 30.

Лемма 3.1. Пусть вершины u, w несмежны и ^ = | [u] П [w] | . Тогда выполняются следующие утверждения:

• (1)    ^ >  6 и Г = u ^ U w ^ в случае ^ = 6;

• (2)    Г не содержит почти хороших пар.

• < Так как k — 2b i + 1 = 6, то ^ >  6, причем в случае ^ = 6 получим Г = u ^ U w ^ . Утверждение (1) доказано.

Пусть ^ = 7, z £ Г — (u ^ U w ^ ) и [z] содержит l вершин из [u] П [w]. По лемме 1.1 имеем ^(u, z) = ^(w, z) и 17 = 2^(u, z) — l, поэтому l нечетно и ^(u, z) = (17 + l)/2.

Пусть X i — множество вершин из ([u] — [w]) U ([w] — [u]), смежных точно с i вершинами из [u] П [w], x i = | X i | . Заметим, что x o = 0, иначе для a £ X o П ([w] — [u]) имеем A(w, a) < 10. Если a £ X i П ([w] — [u]), то либо [а] содержит z и 5 вершин из [u] — [w], либо [а] содержит 6 вершин из [u] — [w]. В любом случае l = 7. Иначе для вершины b £ [u] П [w] П [а] подграф [b] — а ^ содержит u и 6 вершин из [u] П [w], противоречие.

Если l = 1, y £ [u] П [w] П [z], то [y] — z ^± содержит u, w и 6 вершин из [u] П [w], противоречие.

Если l = 7, то P x i = 20, P ix i = 56, P Q) x i =42 и x o + P ( ⁱ 2 ⁱ ) x _i = 6. Отсюда x i = 0 для i > 4, x ₂ = 14 + 2x 4 , x 3 = 6 — 3x 4 и (28 + 4x 4 ) + (18 — 9x 4 ) + 4x 4 = 56, противоречие.

Пусть [u] П [w] П [z] = { y i ,..., y i } . Тогда [y i ] П [y j ] содержит u, w, z, 5 вершин из [u] П [w] и 2 вершины из ([u] — [w]) U ([w] — [u]).

Пусть l = 3. Тогда [y i ] — z ^ содержит u, w и 4 вершины из [u] П [w], поэтому [y i ] П ([w] — [u]) C [z]. Отсюда [y i ] П [y 2 ] содержит по вершине из [u] — [w] и из [w] — [u]. Противоречие с тем, что [у з ] П [u] — [w] содержит не менее двух вершин из [y i ] или из [y 2 ].

Пусть l = 5, Ф = ([u] — [w]) U ([w] — [u]). Тогда [y i ] П [z] содержит 4 вершины из [u] П [w] и 6 вершин из Ф. Если [y i ] П [У 2 ] содержит не более одной вершины из Ф, то [у з ] П Ф содержит не менее трех вершин из [y i ] или из [у ₂ ]. Значит, [y i ] П [y j ] содержит точно две вершины из Ф для любых различных i, j G { 1,..., 5 } . Далее, [у з ] содержит обе вершины из Ф — ([y i ] U [У 2 ]) и не пересекает Ф П [y i ] П [У 2 ]. Противоречие с тем, что [У 5 ] П Ф содержит обе вершины из [у з ] П [У 4 ]. B

До конца параграфа будем предполагать, что Г содержит хорошую пару вершин u, w. Пусть А = [u] П [w], X i — множество вершин из ([u] — [w]) U ([w] — [u]), смежных точно с i вершинами из А, x i = | X i | .

Лемма 3.2. Выполняются следующие утверждения:

• (1)    P x i = 22, P ix i = 60, P ( 2 ) x i = 60;

• (2)    если z G X o П ([w] — [u]), то ^(u, z) = 6 и каждая вершина из [w] П [z] смежна точно с тремя вершинами из [u] — ([w] U [z]), из [u] П [w] и из [u] П [z].

C Подсчитав число ребер между А и ([u] — [w]) U ([w] — [u]), а также число 2-путей с началом и концом в А и средней вершиной в ([u] — [w]) U ([w] — [u]), получим равенства 52 x i = 2 2, 52 ix i = 60, 52 (2)x i = 6 0. Утверждение (1) доказано.

Допустим, что [w] — [u] содержит вершину z из X o . Тогда Г = u ^ U { w, z } U ([w] П [z]).

Допустим, что вершина b из [u] — [w] смежна точно с 1 вершиной из [u] П [w]. Тогда ^(b, z) = 7, противоречие с леммой 3.1.

Если вершина а из [w] П [z] смежна точно с l вершинами из [u] — ([w] U [z]), то [a] содержит w, z, по 6 — l вершин из [u] П [w], [u] П [z] и 3 +1 вершин из [w] П [z]. По лемме 3.1 l 6 4. В случае l = 4 подграф [a] содержит точно две вершины b, b ⁰ из [u] П [w], точно две вершины c, с ⁰ из [u] П [z] и 7 вершин из [w] П [z]. В этом случае [u] — ([a] U [w] U [z]) содержит единственную вершину u ⁰ , и [w] П [z] содержит точно две вершины a ⁰ , a ⁰⁰ вне a ^ . Положим Ф = [a] П [w] П [z]. Рассмотрев почти хорошую тройку (u, w,a), убедимся, что [b] П [b ⁰ ] содержит u, w , a, 4 вершины из [u] П [w], не менее 2 вершин из [u] П [a] и не более одной вершины из Ф. Симметрично, [с] П [с ⁰ ] содержит не более одной вершины из Ф.

Если b смежна с вершиной из { a ⁰ , a ⁰⁰ } , скажем с a ⁰ , то [b] П [b ⁰ ] содержит точно 3 вершины из [u] П [a] — [w] и вершины a ⁰ , a ⁰⁰ несмежны с b ⁰ . Кроме того, [b] П [z] содержит a ⁰ , w, 4 вершины из [a] П [w] и по крайней мере одну вершину из { с, с ⁰ } . Так как ^(b, z) > 7, то b смежна с с, с ⁰ и тройка (z, u, b) является почти хорошей. Далее, вершины с, с ⁰ несмежны с вершиной w из [b] П [z], поэтому [с] П [с ⁰ ] содержит b, u, z, 4 вершины из [u] П [z] и 3 вершины из [b] П [z] (вершину a и 2 вершины из Ф), противоречие.

Итак, { b, b ⁰ ,с, с ⁰ } не пересекает [a ⁰ ] U [a ⁰⁰ ]. Далее, [b] — a ^ содержит u, 4 вершины из [u] П [w] и не более одной вершины из [u] П [z] — { с, с ⁰ } . Поэтому [b] содержит по крайней мере одну вершину из { c, c ⁰ } .

Так как [a0] содержит не менее двух вершин из [u] — ([w] U [z]), то [a] П [u] содержит вершину е, смежную с a0, и |[e] П Ф| 6 4. Далее, степень е в графах [a] П [u], [a] П [a0] не меньше 6, поэтому |[a] П [u] П [a0] | > 3. Симметрично, |[a] П [u] П [a00] | > 3 и [a] П [u] содержит вершину d, смежную с a0, a00. Тогда степень d в графе [a] П [u] не меньше 7, поэтому |[d] П Ф| = 3, и |[a] П [u] П [a0] | = 4. Симметрично, |[a] П [u] П [a00] | = 4. Таким образом, каждая вершина из {b, b0, c, c} смежна с 4 вершинами из ([a] П [u]) — ([w] U [z]). Противоречие с тем, что степень b в графе [a] П [u] равна 5.

Теперь каждая вершина из [w] П [z] смежна не более чем с 3 вершинами из [u] — ([w] П [z]) и по крайней мере с 3 вершинами из [u] П [w]. Но число ребер между [u] П [w] и [w] П [z] равно 30, поэтому каждая вершина из [w] П [z] смежна точно с 3 вершинами из [u] — ([w] П [z]), из [u] П [w] и из [u] П [z]. B

Лемма 3.3. Если х о = 0, то выполняется одно из следующих утверждений:

• (1)    х о = 2,х з = 20;

• (2)    х о = Х 5 = 1, Х 2 = 5, х з = 15;

• (3)    х о = 1,х ₂ = 6, х з = 12, х ₄ = 3.

C Пусть z G Х о П ([w] — [u]), X i = X i П ([u] — [w]), х ⁰ = | X ⁰ | . По лемме 3.2 имеем [w] П [z] С X 3 ([u] П [w]) П X 3 ([u] П [z]) и х о + р С₂1 ) х ⁰ = 11.

Если a G Х 6 , то х о + х 3 = 1 и [u] — [w] содержит 9 вершин из X i U X 2 . Теперь число ребер между [u] П [w] и [u] — [w] равно 30, но не больше 9 • 2 + 3 + 6, противоречие. Пусть a G Х о . Если a G [u] — [z], то a G XgQu] П [z]), противоречие. Если же a G [u] П [z], то ^(a, w) =6 и Г — w ^ = { a, u } U ([a] П [u]). По лемме 3.2 каждая вершина из [a] П [u] смежна точно с 3 вершинами из [u] П [w], поэтому х 3 = 10 и выполняется утверждение (1).

Если a G X 5 , то хд + х 3 = 5 и [u] — [w] содержит 5 вершин из X i U X ₂ . Теперь число ребер между [u] П [w] и [u] — [w] равно 30, но не больше 5 • 2 + 5 • 3 + 5, поэтому х ^ = х 3 = 5 и выполняется утверждение (2).

Если х^ = х 5 = 0, то х ⁰ ₂ + х 3 + х 4 = 11, 2х ⁰ 2 + 3х 3 + 4х 4 = 30 и х 3 + 3х 4 = 11, поэтому х ⁰ ₂ = 6, х ⁰ _з = 2, х ⁰ ₄ = 3. B

Хорошую пару (u, w) назовем парой типа (i), если для нее выполнено утверждение (i) из заключения леммы 3.3.

Лемма 3.4. Граф Г не содержит пар типов (2 — 3).

C Пусть z G X о П ([w] — [u]). Допустим, что [u] П [z] содержит вершину e из X 2 . Положим [e] П [u] П [w] = { f, f ⁰ } и Г — (e ^ U w ^ ) = { g, g ⁰ } . Тогда тройка (w, u, e) является почти хорошей и [f] П [f 0 ] содержит w, u, e, 4 вершины из [u] П [w] и 3 вершины из [w] П [e] (так как подграф [w] П [e] содержит вершину z, не принадлежащую [f ] U [f 0 ]). Отсюда вершины f, f ⁰ не принадлежат [g] U [g ⁰ ].

Пусть Ф i — множество вершин из [w] П [e], смежных точно с i вершинами из { g,g 0 } , y i = | Ф _i | . Тогда f, f 0 ,z G Ф о , у о + y i >  5 (так как Ф о U Ф 1 — { z } содержит вершину, несмежную с f и вершину, несмежную с f ⁰ ) и y 0 + y 2 четно. Отсюда y 0 = y 2 = 3. Для различных h j , h i из Ф ₂ подграф [h j ] П [h i ] содержит e, w, g, g ⁰ и 6 вершин из [e] П [w], поэтому подграф [e] — [w] имеет разбиение на ([e] — [w]) П [h j ], h j G Ф 2 . Противоречие с тем, что u не смежна с вершинами из Ф 2 .

Значит, X ₂ не пересекает [u] П [z]. Пусть (u, w) — пара типа (2) или (3). Тогда X 2 = [u] — ([w] U [z]) и (u, w) — пара типа (2). Далее, число ребер между [u] П [z] и [u] П [w] равно 20, поэтому некоторая вершина из [u] П [w] смежна по крайней мере с 4 вершинами из [u] П [z] и (u, z) — пара типа (2) или (3). Снова X ₂ ([u] П [z]) = [u] — ([w] U [z]) и (u, z) — пара типа (2). Противоречие с тем, что для a G [u] — ([w] U [z]) подграф [u] П [a] содержит по две вершины из [u] П [w], [u] П [z] и не более 4 вершин из [u] — ([w] U [z]). B

Лемма 3.5. Параметр х о равен 0.

C Пусть х о = 0 и для определенности z G X о П ([w] — [u]). Из лемм 2.3, 2.4 следует, что х о = 2, х з = 20 и X о П ([u] П [z]) содержит вершину у. По лемме 2.2 каждая вершина из [y] П [w] — { z } смежна точно с 3 вершинами из [u] П [w]. Поэтому некоторая вершина из

• [u] П [w] смежна точно с 2 вершинами из [у] U [w]. С другой стороны, u Е Х о ([у] П [w]) и по лемме 2.4 имеем | X 2 П ([у] П [w]) | = 0, противоречие. Лемма и предложение 2 доказаны. B

• § 4. Хорошие пары в графах с k > 3bi

В этом параграфе Г является связным реберно регулярным графом с параметрами (v, k, A), k = 3b i + y и Y >  0. По лемме 1.4.2 из [2] Г является графом диаметра 2 с не более чем 2k — 2 вершинами. До конца параграфа будем предполагать, что для некоторой вершины и Е Г подграф ^(u) содержит две вершины w, z, образующие хорошие пары с и. Ввиду леммы 1.5 вершины w, z не смежны. Положим ц = ц(w, z).

Лемма 4.1. Выполняются следующие утверждения:

• (1)    Г ₂ (u) содержится в w ^± U z \ | Г ₂ (и) | = 4b _i — ц и y ( b _i + 1 — Y)(b _i + 1+ Y — ц) делится на 3;

• (2)    ц(u, у) >  b _i + Y +4 для любой вершины у Е Г ₂ (u) — { w, z } ;

• (3)    b 1 + Y + 7 6 Ц 6 2 b _i — 3 и b _i >  Y + 10.

C Для a Е Г ₂ (u) — (w ^± U z ^ ) подграф [a] П [u] не пересекает [w] U [z] и ц(a,u) 6 b _i — y — 2, противоречие. Поэтому ^(u) содержится в w ^ U z ^ . Далее, | [w] — ([u] U [z]) | = | [z] — ([u] U [w]) | = 2b _i — 1 — ц и | Г ₂ (u) | = 4b _i — ц. Так как vkA делится на 6, то y (b i + 1 — Y)(b _i + 1+Y — ц) делится на 3. Утверждение (1) доказано.

Если [z] C [w] U [u], то | Г — (u ^ U w ^ ) | = 1 и по лемме 1.1 имеем ц(u, z) = ц(w,z), поэтому ц = 2b i — 1 = b i + y + 1, k = 4b i — 2, и для вершины a Е [u] П [w] имеем ц(a, z) = 2b i — 2, противоречие. Если ц = b i + y + 1, то по предложению из [1] имеем Y = — 1, противоречие. Значит, ц >  b i + y + 2.

Пусть ц(u, у) = b _i + 2 + y для у Е Г ₂ (u). Если у Е [w] — [z], то [u] П [у] не пересекает [z] и содержит не более одной вершины из [w] и не более b i — 2 — y вершин из [u] — ([w] U [z]), противоречие. Если же у Е [w] П [z], то [u] П [у] содержит не более одной вершины в каждом из графов [w] и [z] и не более b i — 2 — y вершин из [u] — ([w] U [z]), снова противоречие.

Пусть ц(u, у) = b _i +3+y для у Е Г ₂ (u). Если у Е [w] П [z], то по предложению 1 подграф [u] П [у] содержит не более двух вершин в каждом из графов [w] и [z], и ц(u, у) 6 b i — y + 2, противоречие. Если же у Е [w] — [z], [u] П [у] не пересекает [z], содержит не более двух вершин из [w] и ц(u, у) 6 b i — y • Утверждение (2) доказано.

Пусть ц = b _i + y + s. Тогда число ребер между [u] и Г ₂ (u) равно 3b i + b _i Y, но не меньше (3b i — y — s)(b i + Y +4) — 6. Поэтому s >  (b i Y + 12b i — 4y — 6)/(b i + y + 4) и s >  7. Значит, ц >  b _i + y + 7.

Пусть ц = 2b i — 2. Тогда [w] — ([u] U [z]) содержит единственную вершину z * и [z] — ([u] U [w]) содержит единственную вершину w * . Далее, [z * ] — w ^± содержит быть может вершину w ^* и не менее b i — 1 вершин из [u] — ([w] U [z]), противоречие. B

Лемма 4.2. Выполняются следующие утверждения:

• (1)    y + Ц 6 2b i — 3;

• (2)    если ц 6 3b _i /2, то y 6 b _i /3 — 6;

• (3)    если 3b _i /2 < ц, то y < 5b _i /12 — 5.

C Заметим, что | [u] — ([w] U [z]) + | [z] — ([u] U [w]) | = 3b i — y — Ц — 3. Так как вершина из [w] — ([u] U [z]) смежна с b i вершинами из [u] U [z] — [w], то y + Ц 6 2b i — 3. Утверждение (1) доказано.

Пусть ц 6 3b i /2. Тогда число ребер между [u] и ^(u) равно b i (3b i + y ), но не меньше (4b _i — ц)(Ь ₁ + y + 4) — 6. Поэтому (b i + 3b _i Y + 16b _i — 6)/(b _i + y + 4) 6 ц 6 3b _i /2 и

Y 6 b i /3 — 6 — (2b i — 12)/(3b i ). Так как b i >  10, то y 6 b i /3 - 6. Утверждение (2) доказано.

Пусть y = b i /2 — 3 — s, s > 0. По утверждению (1) имеем ^ 6 3b i /2 + s.

Пусть ^ > 3b i /2. Тогда y = b i /2 — 3 — s, s > 0. Далее, число ребер между [u] и Г 2 (и) не меньше (4b _i — ^ — 2)(b _i + y + 4) + 2(b _i + y + 1). Поэтому (b i + 3b _i y + 16b _i — 6)/(b _i + y +4) 6 ^ и b _i + 2y + (12b i — 2y ² — 8y — 6)/(b _i + y + 4) 6 ^ 6 2b _i — 3 — 7. Отсюда — b 2 /2 + 2b _i s + 14b _i — s ² + 2s + 9 6 (6 + 3s — b i /2)(3b i /2 +1 — s) и f (s) = b l /4 — 3b i s + 11b i /2 + 2s ² + 5s + 3 6 0. Заметим, что функция f (s) убывает при s < (3b i — 5)/4 и при s = b i /12 + 2 имеем f (s) > 0. Таким образом, y < 5bi/12 — 5. Лемма, а вместе с ней и теорема доказаны. B