За да се вземат предвид тази и подобни ситуации, естествено е да се въведе следното максимално разпределение
всеки връх и всеки ръб принадлежат към прост цикъл;
всеки два ръба принадлежат на прост цикъл;
за всеки два върха a и b и всеки ръб e има прост (a, b> -верига, съдържаща e;
за всеки три върха a, b, c, съществува проста (a, b) -верига, преминаваща през c.
t> 1) => 2). Нека a и b са два върха на графиката G. Да разгледаме множеството от всички прости цикли на графиката G, съдържащи a. Нека U обозначава множеството от всички върхове, включени в тези цикли. Ясно е, че U не е = празно. Всъщност, прост цикъл, съдържащ a, може да се получи чрез свързване на два ръба ax и ay (x not = y) и проста (x, y) -верига,
не преминава през (съществуващ съгласно свойство 4)). Да предположим, че b не принадлежи на U и не поставяме U = VG \ U. Тъй като графиката G е свързана, тя съдържа ръб zt такъв, че z принадлежи на U, t U (фиг. 34.1). Нека S е прост цикъл, съдържащ a и z. Тъй като G е 2-свързана графика, тя съдържа проста (a, t) -верига P, която не съдържа z. Нека v е първият, броейки от if, връх, включен в S, т.е. (T, v) -подверината на P няма общи върхове с S, различни от v. Сега е лесно да се конструира обикновен цикъл, съдържащ a и t. Получава се чрез комбиниране на (v, z) -верига, влизаща през a и част от S, с ръб и (t, v) -подверига на P (на фиг. 34.1, този цикъл е показан с пунктирана линия ). Следователно, tU; но това противоречи на избора на ръба zt. По този начин не U = , т.е. a и b лежат на общ прост цикъл 2) => 3). Нека a е връх и zt ръб на графиката G, при условие G съдържа цикъл S, преминаващ през върховете a и z са верни. Без загуба на общност ще приемем, че zt z. S. Ако в този случай се окаже, че S преминава през върха t, тогава необходимият цикъл се изгражда по очевиден начин. Нека S не преминава през t. След това помислете за прост цикъл S ', преминаващ през върховете t и a. Такъв цикъл, по условие, съществува. Част от този цикъл е проста верига P, свързваща t с някакъв връх v. S. Верига P може да бъде избрана така, че VP
VS =. Сега желаният цикъл се изгражда по същия начин, както в предишния параграф.
3) => 4). Нека ab и tz са два ръба на графиката G. По хипотеза G има прости цикли S и S ', първият от които съдържа ab и z, а вторият съдържа ab и t. Освен това, желаният цикъл се конструира по същия начин, както в предишните параграфи.
4) => 5). Нека a, .VG, tz.EG. Като е свързана, графиката G съдържа проста верига P = (a, x,. B). Според твърдение 4) графиката G съдържа прост цикъл S, съдържащ ребрата ax и tz. Лесно е да се види, че съединението S U P съдържа необходимата верига.
5) => 6). Нека a, b, cVG, cd.EG. По хипотеза графиката съдържа проста (a, b) -верига, преминаваща през cd и, следователно, съдържаща c.
6) => 1). Нека v . VG. Нека покажем, че графиката G - v е свързана, тоест всяка двойка a, b от нейните върхове е свързана с верига. Всъщност, според твърдението 6), графиката G съдържа проста (v, b) -верига, преминаваща през върха a. Тази верига съдържа (a, b) -подверига, която очевидно не преминава през v и следователно е (a, b>
верига и в графиката G - v.
Ако в изявлението на теорема 34.1 заменим навсякъде думите „проста верига“ и „прост цикъл“ съответно с думите „верига“ и „цикъл“, тогава получаваме подобна теорема за 2-редово свързани графики.
Както беше отбелязано по-горе, при решаването на много задачи върху графики е достатъчно да можете да решите тези „проблеми за всеки 2-свързан компонент на графиката“. Следователно интерес представлява взаимното подреждане на 2-компонентите в графиката.
М
Например графиката, показана на фиг. 34.2, съдържа пет блока Bi (i = 1, 5) (те са заобиколени от пунктирани линии). Сред тези блокове B1, B2 и B3 са 2-свързани графики и всеки от останалите два е ръб.
Изявление 34.2. Всеки два блока на графиката имат най-много един общ връх. По-специално, всеки ръб на графиката е включен само в един от нейните блокове.