Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.

Question

Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.

Answer 1

Предположим, что концы удалённого ребра в новом графе соединены простым путем. Тогда этот путь вместе с удалённым ребром образует в исходном графе цикл.