Пусть G=(V,E) - связный неориентированный граф, на множестве вершин которого определена вещественная функция w. Пусть A - множество ребер, являющееся подмножеством некоторого минимального остова графа G. Пусть (S,V\S) - разрез графа G, согласованный с A, а (u,v) - легкое ребро для этого разреза. Тогда ребро (u,v) является безопасным для A.
Доказательство.
Пусть T- минимальный остов, содержащий A. Предположим, что T не содержит ребра (u,v), поскольку в противном случае доказываемое утверждение очевидно.
Покажем, что существует другой минимальный остов T¢ , содержащий AÈ {(u,v)}, так что ребро (u,v), является безопасным для A.
Остов T связен и потому содержит некоторый (единственный) путь p из u в v; ребро (u,v) замыкает этот путь в цикл. Поскольку вершины u и v принадлежат разным частям разреза (S,V\S), в пути p есть по крайней мере одно ребро (x,y) , пересекающее разрез. Это ребро не лежит в A, так как разрез согласован с A. Добавим к дереву T ребро (u,v) и удалив из получившегося цикла ребро (x,y), получим новый остов T¢ = T\{(u,v) } È {( x,y)}.
Покажем, что T¢ - минимальный остов. Поскольку (u,v) - легкое ребро, пересекающее разрез (S,V\S), изъятое из T ребро (x,y) имеет не меньший вес, чем добавленное вместо него ребро (u,v), так что вес остова мог только уменьшиться. Но остов был минимальным, значит , вес его остался прежним, и новый остов T¢ будет другим минимальным остовом (того же веса). Поэтому ребро (u,v), содержащееся в T¢, является безопасным.