Задание:
Докажите, что если граф связен и не содержит циклов, то в нем n-1 ребро (n — кол-вовершин)
Решение:
Возьмем какую-либо вершину. Просто выбрали любую. Теперь «идем» по ребрам графа, не проходя по каждому ребру более 1 раза. Поскольку циклов нет, рано или поздно мы «упремся» в какую-нибудь вершину, у которой только 1 ребро, по которому мы в нее зашли. Заметим, что тогда ее степень равна 1. Возьмем и выкинем эту вершину и ее единственное ребро из графа. Теперь кол-во вершин в графе — n-1, а ребер m-1 (m — кол-во ребер в изначальном графе). При этом связности мы не испортили, т.к. у нее было только одно ребро, которое мы выкинули с этой же вершиной! Проделаем ту же операцию. Таким образом мы уменьшаем кол-во ребер и вершин каждым шагом на 1. Рассмотрим граф, в котором осталось 2 вершины. Одна из этих вершин имеет степень 1. Значит и вторая тоже (при условии, что нет двойных ребер, но граф связен, поэтому их нет). Уберем последнюю «единичную» вершину. У нас осталась одна вершина и ни одного ребра. А значит вершин изначально было на 1 больше, чем ребер. Доказано.P.S.: Где задачи достал (а)? Какой город?)
Знаете другой ответ?