Изменения
→Доказательство корректности
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E) </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex>.
Тогда после первой итерации алгоритма Борувки получившийся подграф можно достроить до MST.
|proof=Предположим обратное: пусть любое MST графа <tex>G </tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь MST.Тогда существует ребро x из <tex>T </tex> такое что <tex>x </tex> не принадлежит <tex>MST</tex>. Добавив ребро <tex>x </tex> в <tex>MST <tex> получаем цикл в котором <tex>x </tex> не максимально т.к оно было минимальным. Тогда получаем противоречие , исходя из критерия тарьяна, получаем противоречие исходя.
Добав
}}
