Изменения

Необходимо доказать, что если мы возьмем множество ребер <tex>A \in I</tex>, то множество столбцов матрицы инцидентности, соответствующее выбранным ребрам, линейно-независимо, и наоборот, если мы возьмем линейно-независимое множество столбцов, то соответствующее ему множество ребер, не будет образовывать цикла. Докажем эквивалентное утверждение: столбцы линейно-зависимы тогда и только тогда, когда соответствующие им ребра графа <tex>G</tex> содержат цикл.

Если некоторые столбцы матрицы <tex>A</tex> линейно-зависимы, то среди них можно выделить столбцы с нулевой суммой. Есть два варианта:

2) У нас есть столбец <tex>S</tex>, который является суммой остальных столбцов. Этому столбцу соответствует ребро <tex>uv</tex>. Начнем с вершины <tex>u</tex> переходить по другим ребрам из <tex>R \setminus uv</tex> (по каждому ребру проходим только один раз), в итоге мы придем в вершину <tex>v</tex>, так для остальных вершин у нас обязательно будет четное число выходящих из них ребер, потому что иначе на позиции этой вершины в столбце <tex>S</tex> была бы единица (а единицы у нас только на позициях <tex>u</tex> и <tex>v</tex>). Таким образом мы показали, что существует два пути между вершинами <tex>u</tex> и <tex>v</tex> (тот который мы построили и путь по ребру <tex>uv</tex>), значит в выбранном множестве ребер есть цикл.

Если среди данного множества ребер есть петля, то соответствующий ей столбец будет нулевым (по построению матрицы инцидентности), он и обеспечивает линейную-зависимость всего набора векторов.