Вопрос по математике, тема Графы. Докажите, что связный граф, в котором степень каждой вершины чётна, при удалении любого ребра остаётся связным.

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

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

Предположим, что после удаления ребра граф перестаёт быть связным. Значит, после удаления данного ребра граф разбивается на две компоненты связности. Пусть у нас есть две вершины u и v, которые соединены ребром, которое мы удаляем. Поскольку степень каждой вершины чётна, то после удаления этого ребра у вершин u и v по-прежнему будет чётное количество инцидентных рёбер.

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

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