Изменения

<tex> dim(C)=dim(Ker(i))=m-Rang(A) </tex>, где <tex> Rang(A) = </tex> максимальное количество ЛНЗ столбцов <tex> A </tex>. Если рассмотреть цикл в <tex> G </tex>, то , из-за того что каждой вершине инцидентно четное число ребер, сума сумма столбцов соответствующих этим ребрам = 0 значит . Значит, эти столбцы ЛЗ. Отсюда следует, что если любому множеству ребер, содержащих цикл, в соответствие сопоставить набор столбцов из <tex> A </tex> , то он будет ЛЗ. Если же множество ребер не содержит цикл, то набор ЛНЗ (если он ЛЗ, значит коэффициенты взятые из линейной комбинации образуют <tex> x \in C </tex>, значит существует цикл). Максимальное число ребер, которые мы можем выделить из G и которые не содержат цикл <tex>= n - k </tex> (в каждой компоненте связности выделим цикл).