16 Будет ли связным граф, который получится из дерева, если из него удалить: а) ребро, связывающее две неконцевые вершины; б) концевую вершину вместе с выходящим из неё ребром?

Решение:

а) Удаление ребра, связывающего две неконцевые вершины:

Удаление такого ребра в дереве приведет к его разделению на два несвязных компонента (два дерева). Следовательно, полученный граф не будет связным.

б) Удаление концевой вершины вместе с выходящим из неё ребром:

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

Ответ: а) Не будет связным; б) Будет связным.