Задача
COM-B1-M12-P020 Вариант 5. Листья
#20
★★★☆☆ Уровень 3 из 5
Докажите, что в дереве с хотя бы двумя вершинами есть не менее двух вершин степени \(1\).
Возьмите самый длинный простой путь.
Концы самого длинного простого пути не могут иметь дополнительных соседей: иначе путь продолжился бы или появился бы цикл. Поэтому оба конца имеют степень \(1\).
Графовая лемма в краткой форме.