ГДЗ по вероятности и статистике, 7 класс, Высоцкий, номер 16: Дерево случайного эксперимента

Рассмотрим дерево T. Пусть мы удаляем ребро e, которое соединяет две неконцевые вершины (вершины степени больше 1).

Свойство дерева: В любом дереве каждое ребро является мостом. Это означает, что удаление любого ребра из дерева приводит к разрыву единственного пути между концами этого ребра и, как следствие, к разделению графа на две несвязные компоненты.

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

Вывод для а): Граф не останется связным. Он распадется на два отдельных дерева.

Концевая вершина (лист) в дереве имеет степень 1, то есть она соединена ровно с одним ребром. Пусть эта вершина называется v, а её единственный сосед — u.

Операция «удаление вершины вместе с инцидентными ей рёбрами» означает, что мы убираем из графа вершину v и ребро (v,u).

Поскольку вершина v была конечной точкой только одного пути, и этот путь начинался/заканчивался в ней, то все остальные вершины дерева были связаны между собой путями, которые не проходили через v (так как любой путь, проходящий через лист, должен был бы войти в него и выйти обратно по тому же ребру, что невозможно для простого пути между другими вершинами, либо путь просто заканчивается в листе).

Более формально: пусть x и y — любые две оставшиеся вершины. В исходном дереве существовал единственный путь P(x,y). Если этот путь проходил через v, то он выглядел бы как x…u-v-u…y, что невозможно, так как путь не может повторять вершину u без циклов или возврата назад, а в дереве нет циклов. Следовательно, путь P(x,y) не содержал вершину v. Значит, после удаления v и ребра (v,u) путь P(x,y) остается неизменным и полностью принадлежит новому графу.

Вывод для б): Граф останется связным. Оставшаяся часть также является деревом.