Это вопрос № 1-17 в «Руководстве по проектированию алгоритмов, 2-е изд.»by Steven S. Skiena.
Я нашел решение этого вопроса здесь, http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%204.PDF.
Однако я хотел знать, составляет ли это приемлемое доказательство по индукции ?
Базовый случай: когда n = 1, существует один узел без ребер.Очевидно, что существует n - 1 = 1 - 1 = 0 ребер.
Индуктивный шаг:
Предположим, что каждое дерево с n вершинами имеет n - 1кромки.
Учитывая дерево T с n + 1 вершинами, это дерево должно быть эквивалентно дереву из n вершин, T ', плюс1 листовой узел .
По гипотезе ребер (T ') = n - 1 .
Поскольку листовой узел соединен с одним и только с одним другим узлом, то добавление его к T ' добавит только одно ребро.
Поэтому, ребра (T) = ребра (T ') + 1 = n - 1 + 1 = n .КЭД.