Искомое расстояние - есть расстояние В дереве BFS не существует ребер между двумя листамивершинами из разных поддеревьев некоторого их общего предка.
|proof=
Пусть нетПредположим существует, пусть искомое расстояние - есть расстояние между вершинами ребро соединяет вершины <tex>au,bv</tex> где <tex>b</tex> - не является листомиз разных поддеревьев. Т.кРассмотрим первую вершину в которую приведет наш алгоритм. b не является листом, то значит её степень предположим <tex>>u</tex> 1 => из неё существует ребро , тогда в ходе рассмотрения всех смежных вершин мы занесем в непосещенную вершину (дважды посетить список вершину <tex>bv</tex> мы не можем). Лемма доказанатем самым исключим возможность попадания их в разные поддеревья.
}}
{{Лемма|statement=В дереве BFS не существует ребер между вершинами из разных поддеревьев некоторого их общего предка.|proof=Предположим существует, пусть ребро соединяет вершины <tex>u,v</tex> из разных поддеревьев. Рассмотрим первую вершину в которую приведет наш алгоритм. предположим <tex>u</tex>, тогда в ходе рассмотрения всех смежных вершин мы занесем в список вершину <tex>v</tex> тем самым исключим возможность попадания их в разные поддеревья.}}
