Изменения

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