Изменения

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