Изменения

Теперь докажем, что дерево, удовлетворяющее условию, минимально:

Индукция по количеству ребер в дереве:

Переход:

Строим дерево <tex>T'</tex> по лемме о безопасном ребре. Рассмотрим минимальное невзятое ребро <tex>uv \in T</tex>.

Рассмотрим разрез, окружающий одну из двух компонент.

Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>. Рассмотрим <tex>\{ab\} \cup T</tex>: некое ребро <tex>xy \in T</tex>, такое что <tex>w(xy) \ge w(uv) > w(ab)</tex>, будет лежать на цикле. Противоречие условию теоремы.

Если <tex>uv</tex> минимально — добавим его в <tex>T'</tex>.