Деревья и остовные деревья

(a) Проведём индукцию по База для верна. Пусть в любом связном графе с вершиной хотя бы ребра. Покажем, что в связном графе с вершинами хотя бы ребро. Пусть степени всех вершин хотя бы 2. Тогда суммарная степень хотя бы а значит, рёбер хотя бы Пусть нашлась вершина степень которой не более 1. Если ее степень равна 0, то в графе всего 1 вершина, поскольку граф связен, и утверждение задачи верно. Пусть теперь степень равна 1. Тогда удалим эту вершину вместе с исходящим из неё ребром. Предположим, что нарушилась связность. Тогда есть какие-то 2 вершины и путь между которыми обязательно проходил через Но степень равна 1, значит, на пути мы зашли в и вышли по тому же ребру. Тогда рассмотрим такой же путь, но без захода в Так можно удалить все посещения на пути, значит, связность не нарушилась. Тогда можно применить предположение индукции. В графе с удаленной вершиной не менее ребер, следовательно, в исходном графе не менее ребер.

(b) Как и в предыдущем пункте, проведём индукцию по База индукции очевидна. Пусть в дереве на вершине ровно ребра. Найдём висячую вершину (которая всегда существует в дереве) и удалим её. Связность не нарушилась (мы доказывали это в предыдущем пункте), в графе стало на 1 вершину и на 1 ребро меньше. По предположению индукции теперь рёбер значит, изначально их было что и требовалось доказать.