Дано: Нетривиальное дерево.
Найти: Доказать, что в любом нетривиальном дереве имеются, по крайней мере, две висячие вершины.
Решение:
1. Предположим, что в дереве есть только одна висячая вершина.
2. Удалив эту вершину, мы получим две компоненты связности, каждая из которых будет являться деревом.
3. Поскольку исходное дерево было связным, у нас возникает противоречие.
4. Следовательно, предположение о том, что в дереве есть только одна висячая вершина, неверно.
5. Значит, в любом нетривиальном дереве должны существовать по крайней мере две висячие вершины.
Ответ:
В любом нетривиальном дереве имеются, по крайней мере, две висячие вершины, так как удаление одной висячей вершины разбивает дерево на две компоненты связности, что противоречит его определению.