Розкладність графів. Квазіцикли і квазіпромені

Доведення. Оскільки кожен звязний граф має кістяк, ми можемо вважати граф Gr(V,E) деревом. Зафіксуємо довільну вершину xV і назвемо її коренем. Для кожного натурального числа позначимо через Si множину усіх вершин дерева, відстань від яких до кореня дорівнює i. Позначимо через Si' множину всіх вершин ySi, через які проходить скінченне число шляхів з початком у корені x, Si''= Si \ Si'. Розглянемо два випадки.

Випадок 1. Множина Si' скінченна. Нехай Si'={y1,y2,…,yn}. Позначимо через T1, T2,…,Tn дерева з коренями y1,y2,…,yn, що утворюються після видалення вершини x і ребер (x,y1), (x,y2),…,(x,yn). Позначимо через V1,V2,…,Vn множини вершин дерев T1, T2,…,Tn і покладемо X={x}V1V2…Vn. Виберемо довільну вершину yS1'. Якщо S1' покладемо y=x. За теоремою 4.1 існує квазіцикл x1,x2,…,xk , що проходить через усі вершини звязного графа Gr[X'], такий що x1=x, xk=y. Для продовження цього квазіциклу до квазіпроменя виберемо довільну вершину zS1'', суміжну з вершиною x видалимо всі вершини утвореного квазіцикла і до дерева з коренем z застосуємо рекурсію. Врешті решт ми побудуємо квазіпромінь, що виходить з кореня x, враховуючи при цьому ситуації, що можуть виникнути у випадку 2.Випадок 2. Множина S1' нескінченна. Нехай S1'={yn: n}. Позначимо через Tn дерево з коренем yn, утворене видаленням ребра (x,yn). Нехай Vn - множина всіх вершин дерева Tn. Покладемо X={x}nVn. Послідовним застосуванням теореми 1 побудуємо квазіпромінь з початком в x, що проходить через всі вершини звязного графа Gr[X].

Як в першому, так і у другому випадках, вже побудовано квазіпромінь з початком у вершині x. Видалимо з дерева всі вершини, через які проходить цей квазіпромінь. Виберемо найменше натуральне число i, для якого підмножина Si'' не увійшла до утвореного квазіпроменя. Зауважимо, що при цьому Si'=. Виберемо довільний елемент zSi'', через який не пройшов квазіпромінь, і застосуємо рекурсію до дерева з коренем z.

Теорема 4. Нехай Gr(V,E) - довільний нескінченний зв'язний граф. Тоді існує розбиття A множини V на зліченні підмножини, таке що для кожної підмножини AA

(і) граф Gr[A {x}] зв'язний для деякого елемента xV;

(іі) граф Gr[A {x}] є qr-графом з квазіпроменем, що починається з вершини x.

Доведення. Застосуємо схему доведення і позначення теореми 3. Відмінність може виникнути лише у випадку 2. Якщо множина S1' незліченна, то розіб'ємо її на зліченні підмножини і для кожної з них побудуємо відповідний квазіпромінь з початком в корені x дерева Gr(V,E).

Теорема 5. Для кожного нескінченного звязного графа Gr(V,E) і кожного натурального числа r існує розбиття V=V0VVr-1, таке що

dist(V0 ,V1) 3, dist(V1 ,V2) 3,…,dist(Vr-2 ,Vr-1) 3.

Доведення. Розбиття з доведення теореми 2 застосуємо до кожного квазіпроменя, що виникає в процесі доведення теореми 4.

Теорема 5. Нехай Gr(V,E) - нескінченний звязний граф. Тоді існує зліченна сім'я {n: n} розбиттів множини V, така що

(і) |F|=n+1, diam F 3n для всіх F n;

(іі) якщо n+1|m+1, то m є укрупненням розбиття n, тобто кожна підмножина розбиття m є об'єднанням підмножин розбиття n.

Доведення. Скористаємося розбиттям A з теореми 4. Для кожної підмножини AA побудуємо квазіпромінь n , що проходить через усі вершини підмножини A. Розіб'ємо цей квазіпромінь на відрізки

{x0,x1,…,xn}, {xn+1,xn+2,…,x2n+1},{x2n+2,x2n+3,…,x3n+2},…

Одержані відрізки оголосимо підмножинами розбиття n.

Теорема 6. Нехай G - нескінченна група з одиницею e, S - скінченна підмножина групи G, що породжує нескінченну підгрупу, S=S-1, eS. Тоді існує зліченна сім'я розбиттів {n: n} групи G, така що