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

База: если в графе нет циклов, то он уже связный и ничего стирать не нужно.

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

Таким образом, выбирая и стирая ребра циклов, можно постепенно сделать граф связным, не стирая при этом вершины.