Изменения

{{Теорема

|statement=

|proof=

Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Для определенности считаем, что <tex>u</tex> является первой при поиске в глубину. Рассмотрим отрезок <tex>depth[I[u]..I[v]]</tex>. Поскольку этот отрезок {{---}} путь из <tex>u</tex> в <tex>v</tex>, он проходит через их наименьшего общего предка <tex>w</tex>(в дереве есть только один простой путь между вершинами). Покажем, что его глубина минимальна на отрезке <tex>depth[I[u]..I[v]]</tex>. Допустим обратное. Все потомки <tex>w</tex> имеют глубину больше. Но тогда получим, что поиск в глубину вышел из поддерева вершины <tex>w</tex> раньше, чем посетил вершину <tex>v</tex>.