Изменения

|proof=Очевидно, что агоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки мы можем текущее дерево текущий подграф <tex>T</tex> до MST.Докажем это по индукции. 

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