Для доказательства того, что количество листьев в дереве T не меньше, чем наибольшая степень вершины Δ, давайте рассмотрим основные свойства деревьев и их структурные характеристики.

Определение дерева: Дерево — это связный ацикличный граф, в котором любая пара вершин соединена единственным путем.

Определение листа: Лист дерева — это вершина, степень которой равна 1, то есть она соединена только с одной другой вершиной.

Определение степени вершины: Степень вершины — это количество рёбер, соединяющих её с другими вершинами. Вершина с наибольшей степенью в дереве обозначается как Δ.

Теперь давайте разберем, почему k (количество листьев) должно быть больше или равно Δ:

1. В дереве T с n вершинами всегда есть n - 1 рёбер.
2. Каждое ребро соединяет две вершины, и если мы посмотрим на вершину с максимальной степенью Δ, то она соединена с Δ другими вершинами.
3. Из этих Δ вершин, по крайней мере одна из них должна быть листом, так как если все они были бы внутренними вершинами (со степенью больше 1), то это привело бы к увеличению общего числа рёбер, что нарушает свойство дерева.
4. Таким образом, каждая вершина, имеющая степень больше 1, может "передавать" свои рёбра к другим вершинам, но сама по себе должна иметь хотя бы одного листа среди своих соседей.
5. Если бы количество листьев было меньше Δ, то это означало бы, что у нас есть вершины с высокой степенью, не имеющие достаточного количества листьев для соединения, что невозможно в дереве.

Таким образом, мы можем заключить, что количество листьев k всегда будет больше или равно максимальной степени вершины Δ, что и требовалось доказать:

k ≥ Δ