Изменения

 Если если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.

{{Утверждение|statement=Для этого покажем, что для любого разреза <tex>\langle S, T \rangle</tex> исходного графа , в котором ребро <tex>Guv</tex>{{---}} единственное, вес ребра пересекающее его в <tex>uv \in K</tex>, пересекающего этот разрез, вес этого ребра минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез. Действительно, рассмотрим ребро <tex>ab \notin K</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>. По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути. При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве - это <tex>uv</tex>. Таким образом, <tex>w(ab) \ge w(uv) </tex>, ч. т. д.

Найдем теперь минимальное остовное дерево графа используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз. На каждом шаге к строящемуся остову будет добавляться proof=Рассмотрим ребро минимального веса<tex>ab \notin K</tex>, пересекающее <tex>\langle S, пересекающего некоторый разрезT \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>.По условию теоремы, а этот вес, как было показано выше, равен весу <tex>ab</tex> не меньше веса любого ребра на этом пути.При этом <tex>ab</tex> пересекает <tex>\langle S, T\rangle</tex>, пересекающего поэтому на этом пути найдется ребро, пересекающее этот разрез. Поэтому вес получившегося минимального остова Но единственное такое ребро в остовном дереве {{---}} это <tex>Guv</tex> будет равен весу .Следовательно, <tex>Tw(uv) \le w(ab)</tex>, что и требовалось.}}