О дырах и антидырах во вращаемых графах

Известная гипотеза Бержа утверждает, что всякий несовершенный граф содержит порожденный подграф, являющийся дырой или антидырой нечетной длины >  5 [6], [7] (см. также [3, с. 272]). Для некоторых классов графов эта гипотеза доказана (расцепленные и бирасцепленные графы, клетчатые графы и др. [1], [2]). Однако неизвестно — справедлива ли она в классе вращаемых графов (ВГ). Вращаемые графы интересны, в частности, по той причине, что наличие на них естественной алгебраической структуры позволяет строить различного рода контрпримеры в теории графов (см., например, [5]). В работе усиливаются полученные ранее результаты автора [4].

В заметке рассматриваются только неориентированные графы без кратных ребер и без петель. Маршрут в таком графе — это последовательность его вершин, в которой любые две соседние соединены ребром. Цикл — это маршрут, в котором первая вершина совпадает с последней. Если нет других совпадающих вершин, то цикл называется простым. Хорда в цикле — это ребро, соединяющее две несоседние вершины. Дырой в графе называется простой цикл без хорд; длина дыры — это число ее различных вершин (ребер). Антидыра — это порожденный подграф, являющийся дырой в дополнительном графе; длиной антидыры называется число еe различных вершин (но не ребер).

Через N обозначаем множество { 1, 2, 3,... } натуральных чисел; Z — кольцо целых чисел. Для n Е N Z n — кольцо вычетов по модулю n. Множество D С Z n симметрично , если x Е D ^^ — x Е D ^^ n — x Е D. Для симметричного D, не содержащего нуля, вращаемый граф (D) n — это граф с множеством вершин Z n , в котором вершины x и у соединены ребром в том и только том случае, когда x — у Е D.

Для D С Z n \ { 0 } через D' обозначаем множество Z n \ (D U { 0 } ). Ясно, что графы (D) n и (D ^r ) _n являются взаимно дополнительными. Множество D симметрично (при симметричном D), дизъюнктно с D и не содержит нуля.

Элемент x кольца Z _n — это класс всех натуральных чисел, дающих при делении на n один и тот же остаток r x Е N , 0 <  r x < n. Для a,b Е Z n будем писать a < b и a^...b, если r a < r b и, соответственно, r a ^...r b (ясно, что отношение «<» не согласовано с операциями сложения и умножения в Z n ). Очевидным образом интерпретируются фразы

«a ∈ Z n — наименьший элемент множества B ⊂ Z n », «a ∈ Z n — простое число» (последнее, например, означает, что натуральное число r a является простым). Если A ⊂ Z n и A G Z n , то AA — это множество { Ax : x G A } . Через | A | обозначаем число элементов множества A.

Теорема 1. Если n >  5 — простое число, то всякий вращаемый граф с n вершинами, не являющийся пустым или полным, содержит дыру или антидыру (четной или нечетной) длины >  5 .

Для доказательства потребуется ряд вспомогательных утверждений. Обозначим через L класс всех таких графов, которые удовлетворяют условию теоремы и в которых всякая дыра и всякая антидыра имеет длину < 5. Наша цель — показать, что класс L пуст.

Лемма 1. Пусть a,b,c G D , a + b, b + c, c + a G D и a + b + c G D' . Тогда граф (D) n содержит дыру длины >  5 (и потому ( D^ n / L ).

Доказательство. Определим вершины v i графа (D) n следующим образом: v ₀ = 0 G Z _n и V i+1 = E j=₀ X j , где i = 0,1, 2, • • • , n, а X 3t = a, X 3t+i = b и X 3t+2 = c при t = 0,1, 2, • • • . Ясно, что P = v ₀ v 1 v ₂ ••• v n — маршрут в графе (D) n . Так как число вершин, через которые он проходит, больше числа вершин графа (D) n , среди вершин v i найдутся совпадающие. Поэтому можно выбрать такие i и j , что i < j и вершины v _i , v j или совпадают или соединены ребром в (D) n . Среди всех таких пар i, j найдем пару i ₀ ,j ₀ , для которой разность (j — i) минимальна. Из условия леммы вытекает, что j ₀ — i ₀ > 4. Нетрудно убедиться, что вершины v i ₀ , v i ₀ +1 , · · · , v j ₀ -1 , v j ₀ определяют дыру в графе (D) n и длина ее >  5. Лемма доказана.

Рассуждая аналогичным образом и рассматривая суммы v i+1 = ^2j =0 x j , где x _2t = a и x 2 t +1 = b при t = 0, 1, 2, • • • , получим:

Лемма 2. Пусть a,b G D и a + b, 2a + b, a + 2b G D ' . Тогда (D^ n содержит дыру длины >  5 (и потому ( D) _n / L ).

Заменяя в лемме 2 D на D ' и учитывая, что дыры в графе (D) n — это в точности антидыры в дополнительном графе (D ' ) n , мы получим:

Следствие 1. Пусть a,b G D ' и a + b, 2a + b, a + 2b G D . Тогда (D) n / L .

Из следствия 1 (при a = x + 2d и b = — x — d) вытекает следствие 2.

Следствие 2. Пусть x,d,x + 3d G D и x + d,x + 2d G D ' . Тогда (D) n / L .

Нижеприведенную лемму любезно сообщили автору В.А. Гурвич и Е. Борос (E. Boros).

Лемма 3. Пусть A G Z _n , A = 0 и число n просто. Тогда отображение у : (D) n ^ (AD) n графа (D) _n на граф (AD) n , определенное формулой у (x) = Ax , является графовым изоморфизмом (здесь AD = { Ax : x G D } ).

Следствие 3. Пусть ( D^ n — непустой и неполный вращаемый граф, где n — простое число. Тогда: (a) граф ( D) _n изоморфен такому графу (D 1 ) n , что 1 G D 1 и | D | = | D 1 | ; (b) если a,b G D , a G D и ab G D , то граф ( D) _n изоморфен такому графу (D 1 ) _n , что 1 G D 1 и b / D 1 .

При проверке следует использовать отображение у леммы 3 при А = a -1 (в случае (a) в качестве a выбираем произвольный элемент множества D). Напомним, что при простом n кольцо вычетов Z n будет полем.

Лемма 4. Пусть (D) n G L , 1 G D , 2 / D и n — простое число. Тогда:

• (a)    | D | >  k , где k = n ^-1 ;

• (b)    множество D ^′ представимо в виде объединения смежных классов мультипликативной группы поля Z _n по подгруппе H = { 1,2,2 2 ,2 3 , • • •} , состоящей из всех степеней элемента 2 в Z _n .

Доказательство. (a) Допустим, что множество D ^′ содержит два подряд стоящих числа x и x +1. Так как 1 G D, считаем, не теряя общности, что x — 1 G D. Но тогда по лемме 1 (при a = x — 1 и b = c = 1) граф (D) n содержит дыру длины >  5, что невозможно. Противоречие показывает, что выполнено свойство

Если x G D ' , то x + 1 DD.                            ( * )

Так как элементы k и k + 1 взаимно противоположны в поле Z _n , а множество D симметрично, получаем, что они либо одновременно принадлежат, либо не принадлежат множеству D; с учетом (*) заключаем, что k D. Теперь из свойства (*) легко вытекает свойство (a) доказываемой леммы.

• (b)    Допустим, что (b) не выполнено. Тогда найдется элемент a D ^′ , для которого 2a / D ' . По следствию 3 найдется такое множество D 1 С Z _n , что 1 G D' 1 , 2 / D' 1 , а графы (D^ n и с(D ' ) _n изоморфны. Из (D) _n G L , очевидно, следует (D ' ) _n G L . Применяя свойство (a) доказываемой леммы к графу (D' 1 ) _n , получаем | D 1 | > k, что вместе с | D 1 | = | D ' | и | D | >  k дает n = | Z _n | = | D U D' U { 0 }| >  k + k + 1 = n. Полученное противоречие завершает доказательство леммы.

Лемма 5. Пусть 1 G D и 2 / D и n — простое число. Тогда ( D^ n / L .

Доказательство. Допустим, что (D) _n G L . Учитывая, что множества D и D ' являются дополнительными в Z _n \ { 0 } , из свойства (b) леммы 5 заключаем, что D ' представимо в виде объединения смежных классов группы (Z _n \ { 0 } , • ) по подгруппе H = { 1,2,2 2 ,2 3 , •••} . Поэтому из 1 G D вытекает 2 G D. Полученное противоречие завершает доказательство леммы 6.

Из леммы 5 и следствия 3 получаем следующее следствие.

Следствие 4. Пусть ( D^ n G L и n — простое число. Тогда из a G D следует 2a G D .

Лемма 6. Пусть n — простое число, 1,2 G D и 3 / D . Тогда ( D^ n / L .

Доказательство. Допустим, что при некотором a G D, 1 < a < n — 3 верно a + 1, a + 2 G D ' . Тогда (D) _n / L : для проверки следует использовать лемму 1 (при b = 1, c = 2), если a + 3 / D или следствие 2 (при x = a и d = 1) в противном случае. Поэтому из (D) _n G L вытекает, что если x G D ' , то x + 1 G D, то есть выполнено условие (*) леммы 5. Теперь следует повторить (с незначительными изменениями) рассуждения, проведенные при доказательстве упомянутой леммы (используя при этом следствие 4). В качестве H надо взять { 1, 3,3 2 ,3 3 , • ••} .

Доказательство теоремы 1 разбивается на ряд отдельных пунктов. Предположим, что существует граф (D) n , в котором все дыры и все антидыры имеют длину <  4 (то есть (D) n G L ). Не теряя общности, считаем, что 1 £ D (еледствие 3,(a)).

Рассмотрим множество A = { А £ Z n : AD С D } . Из 1 £ D и лемм 6, 7 вытекает 1,2,3 £ A. Если A 1 , A 2 £ A и x £ D, то (A 1 A 2 )x = A 1 (A 2 x) £ A 1 D С D, откуда A 1 A 2 £ A. Поскольку (Z n \ { 0 } , • ) — конечная группа, получаем:

• (1)    (A, • ) — подгруппа мультипликативной группы (Z n \ { 0 } , • ) поля Z n .

Так как Ax = Ay при А £ Z n , А = 0 и различных x, y £ Z n , а Z n конечно, получаем:

• (2)    Если А £ A, то AD = D и AD' = D ' . При этом Ax £ D < >  x £ D и Ax £ D < >  x £ D ' для любого x £ Z n .

Если A £ D, то из 1 £ D получаем A = A • 1 £ AD С D, а потому A С D. По условию граф (D) n не является полным, поэтому множество D ' = Z n \ (D U{ 0 } ) непусто, а потому существует p £ D ' — его наименьший элемент (в Z n ). Если допустить, что p = a • b, где 1 < a <  b < p, то из определения p вытекает a, b £ A, а тогда по свойству (1) p = a • b £ A. Противоречие показывает, что p — простое число. Отметим, что из определения p, а также лемм 6 и 7 вытекает свойство:

• (3)    1, 2, 3,...,p - 1 £ A и p > 3.

Можно также считать, что выполнено свойство:

• (4)    p £ D ' .

В самом деле, из определения p следует, что pa £ D при некотором a £ D. Положим D 1 = a ^-1 D и A 1 = { A £ Z n : AD 1 С D 1 } . Тогда 1 = a ^-1 a £ D 1 . Если A £ A, то AD 1 = A(a ^-1 D) = a ^-1 (AD) С a ^-1 D = D 1 , откуда A £ A 1 . Поэтому { 1, 2, 3, ••• , p — 1 } С A С A 1 . Кроме того, из pa / D вытекает p / D 1 . По лемме 3 графы (D) n и (D 1 ) n изоморфны, поэтому (D 1 ) n £ L . Для завершения доказательства свойства (4) остается D заменить на D ₁ .

Можно считать, что выполнено свойство:

• (5)    | D | <  k.

Если | D | > k, то вместо графа (D) n следует рассмотреть граф (D ' ) n — для него верно (D ' ) n £ L , число p — то же самое, что и для (D) n , а | D ' | = | Z n | — 1 — | D | = = (n — 1) — | D | < (2k + 1 — 1) — k = k.

Из свойств (3),(5) и неравенства p > 3 вытекает:

• (6)    Найдется элемент x £ D ' , для которого x <  k и x /p.

Пусть q — наименьший (в Z n ) элемент множества D ^′ , не делящийся на p. Из определения q и симметричности множества D вытекает:

• (7)    Пусть x £ Z n и 0 < x < q. Тогда, если x £ D ' , то x.p.

Принципиальное значение для дальнейшего имеет свойство:

• (8)    q < 2p.

Предположим, напротив, что q > 2p. Тогда из q /p получаем 2p < q. Пусть a = q, b = —2p, c1 = a + b, c2 = a + 2b и c3 = 2a + b. Тогда a £ D', а из 2 £ A, p / D и свойства (2) вытекает b £ D'. Кроме того, из 0 < c1 < q и c1 /p и свойства

• (7) следует c 1 £ D. Аналогично из 0 < q — p < q вытекает q — p £ D, что вместе

с 2 £ A дает c3 = 2(q — p) £ D. Проверим, что c2 £ D. Ясно, что c2 /p. Если q > 4p, то 0 < c2 < q и соотношение c2 £ D вытекает из определения q. Равенство q = 4p невозможно, поскольку q /p. Пусть теперь q < 4p. Тогда из q > 2p следует 0 < —c2 < 2p < q, а потому снова из определения числа q выводим —c2 £ D, откуда c2 G D ввиду симметричности множества D. Итак c1,c2,c3 G D. Теперь по следствию 1 верно (D)n G L. Противоречие с предположением (D)n G L завершает доказательство свойства (8).

Допустим, что q = xy, где 2 <  x <  y < q. Из q < 2p получаем x,y < p, а тогда x,y G D (свойство (3)) и потому q = xy G A C D. Противоречие с q G D ' показывает, что верно свойство:

• (9)    q — простое число.

Из (7) и (8) получаем:

• (10)    Если p < x < q, то x G D.

• (11)    Пусть x G D' и 0 < x < 3p. Тогда x /3.

Пусть, напротив, x = 3b, где b G N . Тогда 1 < b < p, поэтому b G A C D (свойство (3)). Так как 3 G A, получаем x G D, откуда x / D ' — противоречие.

• (12)    Пусть r = 2q — p. Тогда r /3.

Доказательство. Пусть a = q, b = — p, c 1 = a + b = q — p, c ₂ = a + 2b = q — 2p и c ₃ = 2a + b = 2q — p. Тогда 0 < c 1 < q и c 1 /p, поэтому c 1 G D по свойству (7). Кроме того, из p < q < 2p вытекает 0 <  — c ₂ < p, поэтому (3) дает — c ₂ G D, откуда c ₂ G D. Теперь из условия (D) n G L и следствия 1 получаем c ₃ G D ' . При этом 0 < c ₃ = 2q — p <  2(2p) — p = 3p. Теперь свойство (12) вытекает из (11) и равенства r = С з .

• (13)    Пусть r ' = 4p — q. Тогда r ' /3.

Доказательство. Пусть a = 2p, b = — q, c 1 = a + b = 2p — q, c ₂ = a + 2b = 2(p — q) и c ₃ = 2a+b = 4p — q. Тогда 0 < c 1 < p, 0 <  q — p < q и 0 < c ₃ < 3p (поскольку p < q <  2p). По свойству (3) c 1 G D и q — p G D, что вместе с 2 G A дает c ₂ = — 2(q — p) G D. Теперь условие (D) n G L и следствие 1 показывают, что c ₃ G D ' . Осталось использовать свойство (11) и заметить, что r ' = c ₃ .

• (14)    Хотя бы одно из чисел r, r ' делится на 3.

Это свойство вытекает из того, что простые числа p и q (большие 3) могут давать при делении на 3 только остатки 1 и 2.

Очевидно, свойства (12), (13) и (14) не могут выполняться одновременно. Итак, сделанное в начале доказательства теоремы предположение о существовании вращаемого графа (D n ) G L привело к противоречию. Следовательно, класс L пуст. Теорема 1 доказана.

Вопрос 1. Можно ли усилить формулировку теоремы 1 таким образом, чтобы было гарантировано существование дыры или антидыры нечетной длины >  5?

Вопрос 2. Справедливо ли заключение теоремы 1 в случае, когда число n вершин графа является составным?

Автор глубоко признателен В.А. Гурвичу, В.Н. Лебедеву и Е. Боросу (E. Boros) за постановку и уточнение ряда вопросов, а также за полезные обсуждения.