Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево.
|proof=
[[Файл:Граф_тарьян.png|thumb|right|300x200px|Зеленые ребра принадлежат <tex>T'</tex>, красные принадлежат <tex>T</tex>]]
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:
Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
Теперь докажем, что дерево<tex>T</tex>, удовлетворяющее условию, минимально:
Обозначим дерево Для этого заметим, что для любого разреза <tex>\langle S, T\rangle</tex> исходного графа <tex>G</tex>, вес ребра <tex>uv \in T</tex>, пересекающего этот разрез, минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез. Действительно, рассмотрим ребро <tex>ab \notin T</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и покажем, что его можно построить алгоритмом Краскала<tex>b</tex> по дереву <tex>T</tex>.
Индукция по количеству ребер По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути. При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве:- это <tex>uv</tex>. Таким образом, <tex>w(ab) \ge w(uv) </tex>, ч. т. д.
'''База:''' пустое Найдем теперь минимальное остовное дерево. '''Переход:''' Строим дерево <tex>T'</tex> по лемме графа используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз. Рассмотрим минимальное На каждом шаге к строящемуся остову будет добавляться ребро <tex>uv \in Tминимального веса, uv \notin T'</tex>. Рассмотрим пересекающего некоторый разрез по этому ребру <tex>(U,V): u \in Uа этот вес, v \in V</tex>. Пусть <tex>uv</tex> не минимально в разрезекак было показано выше, тогда существует равен весу ребра <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>пересекающего этот разрез. Рассмотрим Поэтому вес получившегося минимального остова <tex>\{ab\} \cup TG</tex>: некое ребро будет равен весу <tex>xy \in T</tex>, такое что <tex>w(xy) \ge w(uv) > w(ab)</tex>, будет лежать на цикле <tex>C</tex>. Противоречие условию теоремы. Если <tex>uv</tex> минимально — добавим его в <tex>T'</tex>. В процессе индукции добавлялись только ребра из <tex>T</tex>, поэтому построенное дерево <tex>T'</tex> совпадет с <tex>T</tex>и требовалось.
}}
