G=(V,E)

Коцикл – минимальное количество ребер при удалении одного из них граф теряет связанность. C=E`E   G`=(V,E\C)

Минимум: Что ни какое собственное подмножество С этим свойством не обладают

{x₁,x₂}  -  коцикл                                                                                x₃      ^x1

{x₁,x₂,x₃}   -  не является коциклом, т.к. {x₁,x₂} его подмножество              _x2

Определение:  Пусть есть связанный граф G=(V,E)

C – его коцикл

G=(V,E\C)

Получим у G` несколько компонент связности k>=2

Пусть k=3

(V₁,E₁), (V₂,E₂), (V₃,E₃)

т.к. G связан, то существует ребро x, которое соединяет (V₁,E₁) и (V₂,E₂) и оно принадлежит С, тогда если рассмотреть множество С-х  (С\{x}), то все равно граф несвязан, но мы получим множество С-х – коцикл, этого не может быть, т.к. мы предположили, что k=3, a k=2, т.е. при удалении ребер принадлежащих С, граф распадается на 2 компоненты связности.

Ребра коцикла обладают свойством: (они не соединяют V₁ и E₁, V₂ и E₂), они должны соединять V₁ и V₂.

 Теорема: 53 При удалении ребра коцикла, он распадается на 2 компоненты связности и ребра коцикла соединяют вершины одной компоненты связности с другой.

Следствие: Любой Цикл и любой коцикл связанного графа имеют четное число общих ребер.

Доказательство

(1)=а=(2)

1. Если цикл принадлежит (1) и  не пересекается с ребром коцикла, четно.
2. Если цикл пересекается с ребрами, коцикла, то нужно пройти четное число раз, туда и обратно.

Каждой ветви каркаса ставиться главный цикл.

Есть связанный граф C=(V,E), есть каркас.

<[]

T=(V,E) рассмотрим модуль, ветвь этого каркаса – она является коциклом для дерева (каркаса) и ребро разобьется на 2 компоненты связности.

(V₁,E₁`), (V<sub>2</sub>,E<sub>2</sub>`)

Е`` - ребра, которые являются хордами исходного графа, которые соединяют V₁–V₂ тогда главный коцикл – эти хорды + та ветвь, которую удалили.

Число главных коциклов – это коранг графа.