Решение задачи 260

Условие:

Верно ли, что из всякого связного графа можно удалить вершину и все выходящие из нее ребра так, чтобы он остался связным?

Решение:

Да, верно. Пусть дан граф. Введем некоторые определения:

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

Напомним, что деревом называется связный граф без циклов.

Пусть дан связный граф.

Остов: подграф, являющийся деревом и содержащий все вершины исходного графа.

Утверждение: во всяком связном графе есть остов.

Доказательство: если данный граф дерево, то он и является остовом. Если он не дерево, то в нем есть цикл. Удалим любое ребро из этого цикла, тогда связность не потеряется. Будем повторять эту процедуру пока граф не станет деревом.

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

Ответ: Да, верно.