Давайте разберем данное утверждение шаг за шагом и докажем его.

Мы знаем, что дерево T — это связный граф без циклов. В дереве есть особые вершины, которые называются листьями. Листья — это вершины, имеющие степень 1, то есть они соединены только с одной другой вершиной.

Обозначим:

• Δ — наибольшая степень вершины в дереве T.
• k — количество листьев в дереве T.

Теперь давайте проанализируем вершины дерева:

1. Согласно определению, степень вершины — это количество рёбер, исходящих из этой вершины. Если вершина имеет степень Δ, то она соединена с Δ другими вершинами.
2. Каждая из этих Δ вершин, с которыми соединена вершина максимальной степени, может быть либо внутренней (т.е. не листом), либо также листом.
3. Если хотя бы одна из этих Δ вершин является внутренней, то она должна иметь по меньшей мере одну связь с другой вершиной, кроме как с вершиной максимальной степени. Это означает, что у нас есть возможность создать дополнительные листья в дереве.
4. Если все Δ вершин являются листьями, то мы имеем как минимум Δ листьев.

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

k ≥ Δ.

Это завершает наше доказательство. Мы показали, что количество листьев в дереве всегда будет больше или равно максимальной степени любой вершины в этом дереве.