Доказываем корректность поиска диаметра дерева

Пара рисунков в статью улучшила бы восприятие текста. Например, визуализировать разные варианты деревьев.

Плохое доказательство.
Какое-то месиво.

BFS, LCA

От того, что вы пишете по-инострански, вы выглядите не круто, а наоборот.

Найдем НОП этих вершин...

Что такое "общий предок" вершин?

… диаметр "перегибается"...

Что это означает?

Зачем-то LCA вводить… Дальше как в викторине: «А я могу доказать теорему за пять строчек»(на достаточно широком экране 8)):
Есть первая вершина V, есть самый длинный путь в дереве AB. U — самая удаленная от V. X — вершина в AB, ближайшая к V. Пусть d(X,A) >= d(X, B) (перестановку А и B выбираем мы)
Далее, X лежит на пути UV, т.к. иначе d(U, A) > d(B, A).
Дальше, d(U, X) >= d(X, A), т.к. иначе d(V, A) > d(V, U). Значит, d(U,A) = d(U,X) + d(X, A) >= d(B,X) + d(X,A) = d(A,B).
Значит, вершина U лежит хотя бы на одном самом длинном пути.

Помоему это очевидно в случае дерева. Первый проход из любой вершины находит один конец диаметра, второй проход находит сам диаметр. Или я чего-то не понимаю?

> Сначала поймем, что искомое расстояние — расстояние между двумя листами

контрпример: A->B->C->D
диаметр 3 (A,D) при этом A не является листом

да и на вашем примере — для двух вершин — одна из них не будет листом.

Здесь выполняется не поиск в ширину, а полный обход дерева в произвольном порядке. (Технически удобнее — обход в глубину).
Потому что поиск в ширину предполагает определённый порядок обхода (по возрастанию расстояния от корня) и остановку на искомой вершине.
Нам же нужно взять любую самую удалённую вершину и убедиться, что ещё более удалённых нет.

Кстати, несложно показать, что если от стартовой вершины наиболее удалены несколько вершин, то можно брать любую из них.