Номер 10, страница 8, часть 2 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

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

В дереве с 4 вершинами может быть 2 или 3 концевые (листовые) вершины. Ниже представлено развернутое решение, объясняющее, почему это так, и примеры для каждого возможного случая.

Для анализа воспользуемся основными свойствами графа-дерева. Для дерева с 4 вершинами ($n=4$) справедливо следующее:
1. Количество ребер равно $m = n-1 = 4-1=3$.
2. Сумма степеней всех вершин равна удвоенному количеству ребер (согласно лемме о рукопожатиях): $\sum \text{deg}(v) = 2m = 2 \times 3 = 6$.
3. Концевая вершина — это вершина со степенью 1.
4. Любое дерево с $n \geq 2$ вершинами имеет как минимум две концевые вершины. Этот факт сразу исключает возможность существования дерева с 0 или 1 концевой вершиной.

Рассмотрим все возможные случаи для количества концевых вершин.

2 концевые вершины

Если в дереве 2 концевые вершины, то их степени равны 1. Две оставшиеся (внутренние) вершины должны иметь степень не менее 2. Обозначим степени вершин как $d_1, d_2, d_3, d_4$.
Пусть $d_1=1$ и $d_2=1$. Для двух других вершин $d_3 \geq 2$ и $d_4 \geq 2$.
Используя свойство суммы степеней: $d_1 + d_2 + d_3 + d_4 = 1 + 1 + d_3 + d_4 = 6$.
Отсюда следует, что $d_3 + d_4 = 4$.
Единственное решение для этого уравнения в целых числах при условии $d_3, d_4 \geq 2$ — это $d_3 = 2$ и $d_4 = 2$.
Таким образом, мы ищем дерево с набором степеней вершин $\{1, 1, 2, 2\}$. Такое дерево единственно (с точностью до изоморфизма) и представляет собой граф-путь (цепь).

Пример: Вершины 1, 2, 3, 4 соединены последовательно ребрами (1,2), (2,3), (3,4). Граф выглядит как 1—2—3—4. Вершины 1 и 4 имеют степень 1 и являются концевыми. Вершины 2 и 3 имеют степень 2.
Ответ: Дерево-цепь (граф-путь), в котором четыре вершины соединены последовательно, например, 1—2—3—4.

3 концевые вершины

Если в дереве 3 концевые вершины, то их степени равны 1. Оставшаяся одна вершина должна иметь степень не менее 2.
Пусть $d_1=1, d_2=1, d_3=1$. Для четвертой вершины $d_4 \geq 2$.
Сумма степеней: $d_1 + d_2 + d_3 + d_4 = 1 + 1 + 1 + d_4 = 6$.
Отсюда $3 + d_4 = 6$, что дает $d_4 = 3$.
Набор степеней вершин в таком дереве: $\{1, 1, 1, 3\}$. Этому набору соответствует граф-звезда.

Пример: Одна центральная вершина (например, вершина 4) соединена с тремя остальными (1, 2, 3). Рёбра: (4,1), (4,2), (4,3). Вершины 1, 2 и 3 не соединены между собой. Они имеют степень 1 и являются концевыми. Центральная вершина 4 имеет степень 3.
Ответ: Дерево-звезда, в котором одна центральная вершина соединена с тремя остальными.

Анализ невозможных случаев

- 0 или 1 концевая вершина: Как было упомянуто, любое дерево с 2 или более вершинами имеет как минимум 2 концевые вершины, поэтому эти случаи невозможны.
- 4 концевые вершины: Если бы все 4 вершины были концевыми, степень каждой была бы равна 1. Сумма степеней была бы $1+1+1+1 = 4$. Это противоречит тому, что сумма степеней в дереве с 4 вершинами должна быть равна 6.