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