Question

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

Answer 1

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

Answer 2

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

Для начала, давайте определим дерево: дерево - это связный граф без циклов. То есть между любыми двумя вершинами в дереве существует единственный путь (нет нескольких путей, приводящих к тем же вершинам) и нет замкнутых циклов.

Доказательство по индукции:

Шаг базы: Рассмотрим дерево из одной вершины - это единственная вершина без ребер. Очевидно, что удалив любое ребро (так как оно единственное), дерево становится несвязным графом (просто станет набором изолированных вершин).

Шаг индукции: Предположим, что утверждение верно для дерева с N вершинами (при N ≥ 1) и пусть это дерево имеет N-1 ребро. Докажем, что если мы удалим любое ребро из такого дерева, оно станет несвязным.

Теперь добавим новую вершину к дереву, соединим ее с одной из существующих вершин, чтобы получить дерево с N+1 вершиной и N ребрами. Поскольку это дерево имеет N+1 вершину и N ребер, оно всё равно удовлетворяет определению дерева и связанности.

Теперь рассмотрим удаление ребра из этого нового дерева. Существует два случая:

1. Удаляем ребро, которое соединяет новую вершину с существующим деревом. В этом случае новая вершина становится изолированной, и дерево разбивается на две отдельные компоненты связности. Это означает, что дерево стало несвязным графом.

2. Удаляем ребро, которое находится внутри существующего дерева. По предположению индукции, такое дерево без этого ребра остается связным. Удалив ребро, мы лишь уменьшаем количество ребер, но связность остается. Дерево с N+1 вершиной и N-1 ребром остается связным.

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