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