Я пытаюсь использовать индукцию здесь, чтобы показать это, я застрял в индуктивном шаге.
Пусть $ s $ - исходная вершина $ T $, и мы применяем BFS из $ s$.
База (1 вершина): этот случай тривиален, когда у нас есть только $ s $.
Индуктивная гипотеза: T - остовное дерево до вершины $ v_ {k-1}$.
Индуктивный шаг: когда мы обнаруживаем вершину $ v_k $, мы окрашиваем ее в серый цвет (обнаружен), тогда ее расстояние от $ s $ равно $ v_ {k-1} .d + 1 $ и затем ставится в очередь.
Мой вопрос здесь - достаточно ли моего индуктивного шага для этого доказательства, или мне нужно каким-то образом показать, что следующая обнаруженная вершина имеет расстояние плюс предыдущее расстояние?