Изменения

* Переход: Пусть лес <tex>T</tex> получившийся после <tex>n</tex> итераций алгоритма можно достроить до MST. Докажем что после <tex>n + 1</tex>-й итерации получившийся лес <tex>T'</tex> можно достроить до MST.Предположим обратное: <tex>T'</tex> нельзя достроить до MST. Тогда существует <tex>F</tex> = MST графа <tex>G</tex>, содержащее <tex>T</tex> и не содержащее <tex>T'</tex>. Тогда рассмотрим цикл получающийся добавлением в <tex>F</tex> какого-нибудь ребра <tex>x</tex> из <tex>T'</tex> - <tex>T</tex>. На этом цикле имеется ребро большее по весу чем ребро <tex>x</tex>, иначе компонента для которой <tex>x</tex> было является минимальным ребром ни с кем больше ни связана.Следовательно исходя Исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия тарьяна мы получили Тарьяна]] получаем противоречие.Получаем <tex>T'</tex> можно достроить до MST. Следовательно предположение индукции верно.