7. В связном графе 100 вершин и 200 рёбер. Докажите, что можно стереть несколько рёбер, образующихцикл так, чтобы граф остался связным. (Вершины не стираем!)

Предыдущий
вопрос Следующий
вопрос

Докажем данное утверждение по индукции.

База индукции: При 1 цикле (3 вершины и 3 ребра) очевидно, что можно стереть хотя бы одно ребро, чтобы граф оставался связным.

Шаг индукции: Пусть для графа с n вершинами и m рёбрами выполнено утверждение. Добавим к графу еще одну вершину и одно ребро. По предположению индукции, в оставшемся графе можно стереть несколько рёбер, образующих цикл так, чтобы граф остался связным. Теперь вернем стертое ребро. Если это ребро не входит в цикл, то граф останется связным. Если же это ребро принадлежит циклу, то стерев одно из рёбер цикла, граф останется связным.

Таким образом, для графа с 100 вершинами и 200 рёбрами можно стереть несколько рёбер, образующих цикл, чтобы граф остался связным.