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

Предположим, что после удаления ребра между вершинами $ v_1 $ и $ v_2 $ граф разбился на 2 компоненты
связности A и B.
Рассмотрим компоненту A: в ней вершина $ v_1 $ имеет нечетную степень, а все остальные вершины –
четную. Тогда сумма степеней всех вершин в этой компоненте нечетна – противоречие.
Тогда граф не мог разбиться на 2 компоненты связности ⇒ остался связен.


info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp