Задача
Докажите, что граф, в котором каждые две вершины соединены ровно одним простым путем, является деревом.
Решение
Очевидно, что данный граф связен. Предположим теперь, что в нем есть цикл. Тогда любые две вершины этого цикла соединены по крайней мере двумя простыми путями. Противоречие.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет