Пусть T - минимальное весовое остовное дерево, а vw - самое легкое ребро, инцидентное v. Пусть P - уникальный путь в T между v и w. Если P не является самим vw, то он содержит некоторое другое ребро vx. Пусть T 'будет множеством ребер, полученных из T путем вставки vw и удаления vx. Я утверждаю, что (1) T ', по крайней мере, так же легок, как и T, поскольку vw, по крайней мере, так же легок, как vx (2). T' - это дерево, поскольку оно соединяет все (для каждой прогулки в T выведите связанную прогулку в T 'с теми же конечными точками путем замены vx на vw и остальной части P) и имеет правильное количество ребер, следовательно (3) T' является остовным деревом с минимальным весом, который содержит vw.