Изменения
→Корректность
|statement=
|proof=
Зафиксируем любое дерево путей и покажем, что в графе <tex>G</tex> найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одному ребру. Меньше быть не может, иначе получится отдельная компонента связности. Если же в какое-то подмножество входит больше чем одно ребро, то все ребра кроме одного можно заменить ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.