Условие
В дереве 4 вершины. Сколько концевых вершин в нём может быть? Приведите пример дерева для каждого возможного значения.
Идея решения. В дереве с 4 вершинами ровно 3 ребра. Выясняем, сколько концевых вершин может получиться при таком числе рёбер.
Решение
Сколько рёбер
По свойству 3 в конечном дереве рёбер на 1 меньше, чем вершин: ребра.
Меньше двух концевых не бывает
Пройдём по дереву самой длинной цепью. Её последняя вершина — концевая: если бы из неё выходило ещё одно ребро, оно вело бы либо в новую вершину (тогда цепь была бы длиннее), либо в уже пройденную (тогда получился бы цикл). То же верно для первой вершины цепи. Значит, концевых вершин не меньше двух.
Все 4 концевыми быть не могут
Тогда из каждой вершины выходило бы одно ребро, а каждое ребро соединяет две вершины. Рёбер было бы , а их должно быть 3.
Примеры
2 концевые вершины — у цепи из 4 вершин. 3 концевые — у «звезды»: одна вершина соединена с тремя остальными.
Деревья с 4 вершинами: цепь (2 концевые) и «звезда» (3 концевые); концевые выделены синим
Ответ
2 или 3 концевые вершины (примеры: цепь и «звезда»)
✓ Ответ проверен вычислением