Изменения

Очевидно, что максимальное ребро в MST минимально. Пусть мы построили алгоритмом Краскала минимальное остовное дерево и его максимальное ребро не минимально. Иначе говоря, в разрезе, который пересекает максимальное ребро, есть ребро с меньшим весом, но это противоречит тому, что алгоритм Краскала построил строит MST. Аналогично в максимальном остовном дереве минимальное ребро максимально. Такое дерево можно построить, заменив веса ребер на значения с противоположным знаком и запустив алгоритм поиска MST. В конце нужно не забыть снова изменить знаки.