Вопрос школьника
Докажите, что для любого дерева, имеющего В вершин и Р рёбер, справедливо соотношение Эйлера: В — Р = 1.
Ответ от учителя
Для доказательства соотношения Эйлера для дерева с В вершинами и Р ребрами, можно воспользоваться индукцией по числу вершин.
База индукции: для дерева с одной вершиной (В=1) и без ребер (Р=0) соотношение Эйлера выполняется: 1-0=1.
Шаг индукции: предположим, что для любого дерева с числом вершин меньше n, соотношение Эйлера верно. Рассмотрим дерево с n вершинами и Р ребрами.
Выберем любую вершину в дереве и удалим ее вместе со всеми инцидентными ей ребрами. Получим два поддерева, каждое из которых является деревом меньшего размера, чем исходное дерево. По предположению индукции, для каждого из этих поддеревьев выполняется соотношение Эйлера: В1-Р1=1 и В2-Р2=1.
Общее число вершин в этих поддеревьях равно n-1, а общее число ребер равно Р. После удаления одной вершины и всех инцидентных ей ребер, число вершин уменьшилось на 1, а число ребер уменьшилось на количество ребер, инцидентных удаленной вершине. Таким образом, Р1+Р2+1=Р.
Сложим соотношения для каждого из поддеревьев и учтем, что общее число вершин в дереве равно В=В1+В2+1:
(В1-Р1) + (В2-Р2) = 2
В1+В2+1 — (Р1+Р2+1) = 2
В-Р=1
Таким образом, для любого дерева с В вершинами и Р ребрами, справедливо соотношение Эйлера: В-Р=1.
