Упр.90 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 90. Докажите, что в дереве с л вершинами количество рёбер равно (n-1).

Докажем утверждение по индукции по числу вершин дерева.

1. Если в дереве одна вершина, то рёбер нет. Значит, $$n=1,\quad m=0,$$ и формула $$m=n-1$$ верна.

2. Предположим, что для любого дерева с $$n$$ вершинами число рёбер равно $$n-1.$$

Рассмотрим дерево с $$n+1$$ вершинами. В дереве всегда есть висячая вершина, то есть вершина степени 1. Удалим её вместе с инцидентным ребром. Тогда получится снова дерево, но уже с $$n$$ вершинами.

По предположению индукции в этом дереве $$n-1$$ ребро. После удаления одной вершины и одного ребра в исходном дереве было на одно ребро больше, то есть

$$m=(n-1)+1=n.$$

Следовательно, для дерева с $$n+1$$ вершинами число рёбер равно $$n=(n+1)-1.$$

Таким образом, для любого дерева с $$n$$ вершинами число рёбер равно $$n-1.$$

Ответ

В дереве с $$n$$ вершинами число рёбер равно $$n-1.$$