Идея. Свойство 3 из §47*: в конечном дереве число рёбер на 1 меньше числа вершин. Значит, вершин на 1 больше, чем рёбер.
1Это свойство доказывается в учебнике удалением концевых вершин: каждый раз убираем одну вершину и одно ребро, пока не останется одна вершина без рёбер. Поэтому разница всегда равна 1.
2Применяем её три раза: к числу рёбер прибавляем 1, получаем число вершин.
Частая ошибка. Перепутать направление: вершин на 1 больше, а не меньше. Проверка на маленьком примере: у одного ребра две вершины.
