4.5. Связь между подпространствами циклов и разрезов
В данном разделе мы дадим характеризацию подграфов в пространстве циклов графа G в терминах подграфов подпространства разрезов того же графа.
В разд. 2.8 (теорема 2.14) мы доказали, что цикл и разрезающее множество имеют четное количество общих ребер. Используя то, что каждый подграф в подпространстве циклов графа является либо циклом, либо объединением реберно-непересекающихся циклов, а каждый подграф в подпространстве разрезов — разрезающим множеством или объединением реберно-непересекающихся разрезающих множеств, получим следующую теорему как непосредственное следствие теоремы 2.14:
Теорема 4.7. Любой подграф в подпространстве циклов графа G имеет четное число общих ребер с любым подграфом в подпространстве разрезов того же графа. В теореме 4.8 мы докажем обратное утверждение.
Теорема 4.8.
1. Подграф графа G принадлежит подпространству циклов графа G, если он имеет четное число общих ребер с любым подграфом в подпространстве разрезов графа G.
2. Подграф графа G принадлежит подпространству разрезов графа G, если он имеет четное число общих ребер с любым подграфом в подпространстве циклов графа G.
Доказательство. 1. Не нарушая общности, можно предложить, что G — связный граф. Аналогично доказывается случай, когда граф G несвязный. Пусть Т — остов графа G. Обозначим ветви остова Т через 
а хорды — через 
Рассмотрим любой подграф С графа G, имеющий четное число общих ребер с любым подграфом в подпространстве разрезов графа G. Предположим, не нарушая общности, что подграф С содержит хорды 
Обозначим через С кольцевую сумму базисных циклов 
по отношению к хордам 
. Очевидно, что С содержит только хорды 
. Следовательно, 
не содержит ни одной хорды. Поскольку С — кольцевая сумма нескольких циклов графа G, то это множество имеет четное число общих ребер с каждым подграфом в подпространстве разрезов графа G. Из того, что С также обладает этим свойством, следует, что им обладает и 
. Теперь убедимся, что 
— пустое множество. Если это не так, то 
состоит только из ветвей. Пусть 
— любая ветвь в 
. Тогда 
— единственное общее ребро между 
и базисным разрезающим множеством по отношению к 
Однако это невозможно, так как 
должно иметь четное число общих ребер с любым разрезающим множеством. Таким образом, 
должно быть пустым. Другими словами 
и, следовательно, С принадлежит подпространству циклов графа 
2. Доказательство этой части теоремы аналогично.
