в дереве 4 вершины. сколько концевых вершин в нём может быть? приведите пример дерева для каждого возможного значения

Задача сводится к числу листьев (концевых вершин) в дереве из 4 вершин.

• В дереве сумма степеней вершин равна 2(n−1) = 2·3 = 6.
• Пусть L — число листьев (вершин степеней 1). Остальные вершины (4 − L) имеют степень не меньше 2.

Получаем неравенство: 6 ≥ L + 2(4 − L) = 8 − L, отсюда L ≥ 2. Также L не может быть 4 (если бы все вершины были листами, сумма степеней была бы 4, а не 6), поэтому L ≤ 3.

Итак, возможны значения L: 2 или 3.

Примеры для каждого значения:

• L = 2 (два листа): прямая цепь из 4 вершин Вершины: 1 — 2 — 3 — 4 Листья: 1 и 4.
• L = 3 (три листа): звезда K1,3 Центр: 1, листа: 2, 3, 4 Граф: 1 соединён с 2, 3 и 4.

Замечание: это два неэквивалентных типа деревьев на 4 вершины (есть только две непересекающиеся конфигурации): путь P4 и звезда K1,3.