Изменения
Нет описания правки
|proof=
Пусть нет, пусть искомое расстояние - есть расстояние между вершина a, b, где b - не является листом.Т.к. b не является листом, то значит её степень > 1 => из неё существует ребро в непосещенную вершину (дважды посетить вершину b мы не можем). Лемма доказана.
}}
Запустив BFS от произвольной вершины. Мы получим дерево BFS.
{{Теорема. |statement=В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого из общего предка.Доказательство |proof=Точно такое-же как про дерево DFSу дерева dfs.}}
Мы свели задачу к нахождению вершины v, такой, что сумма глубин поддеревьев максимальна.
