Предположим противное: пусть остовное дерево <tex> A </tex> состоит из всех минимальных ребрах на циклах, тогда оно не минимально.
Попробуем найти цикл в графе Если <tex> G A </tex>не минимально, то его можно улучшить, в котором значит есть ребро <tex> (u, v) \notin A</tex>, которое имеет наименьший вес на цикле и которое легче остальных ребер этого цикла, включая ребро <tex> (a, b) \in A</tex>не принадлежит дереву. ОчевидноСледовательно, что таких пар ребер найти нельзя, так как <tex> A </tex> состоит из ребер наименьшего веса дерево построено не на минимальных ребрах в циклах. Поэтому остовное дерево <tex> A </tex> нельзя улучшить, следовательно оно минимальное {{---}} противоречие.
<tex> \Leftarrow </tex>
