Изменения

Осталось доказать, что всегда выполняется неравенство <tex>I[u] \le I[w] \le I[v]\;(*).</tex>

Пусть вершина <tex>u</tex> посещается раньше, чем вершина <tex>v.</tex> Тогда, если вершина <tex>v</tex> не явлется потомком вершины <tex>u,</tex> будет выполняться неравенство <tex>\;(*)</tex> (так как после посещения поддерева, содержащего вершину <tex>u</tex>, в список будет добавлена вершина <tex>w</tex>, а после - вершина <tex>v</tex>). А если вершина <tex>u</tex> является предком вершины <tex>v,</tex> то вершина <tex>u</tex> будет наименьшим общим предком вершин <tex>u, v</tex>. Очевидно, что неравенство выполняется.

== Сложность ==