Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
|proof=
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально.
Если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом, добавив это ребро в остов, и удалив самое тяжелое ребро из цикла. Если же это условие не выполнилось ни для одного ребра, то вес остова при добавлении не изменится.
Теперь, рассмотрим Рассмотрим общий алгоритм построения минимального остовного дерева <tex> A </tex>, но сначала надо ознакомиться , ознакомившись с определением [[Лемма о безопасном ребре|леммой о безопасном ребребезопасного ребра]].
'''function''' Generic MST(<tex> G </tex>):
<tex> A = A \cup \{( u, v )\} </tex>
'''return''' <tex> A </tex>
В результате алгоритма получится минимальное остовное дерево <tex> A </tex>, состоящее полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро.
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально.
Если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом, добавив это ребро в остов, и удалив самое тяжелое ребро из цикла. Если же это условие не выполнилось ни для одного ребра, то вес остова при добавлении не изменится.
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.
}}
