Изменения

<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> (в каждой компоненте связности выделим цикл).