Докажите, что при n ⩾ 1 связен любой граф на 2n + 1 вершине, степень каждой из которых не меньше n.

Предположим, что такой граф не связен. Рассмотрим компоненты связности, на которые разбился
граф. В каждой из этих компонент степень каждой вершины хотя бы n, тогда в каждой компоненте
хотя бы n + 1 вершин. Тогда всего в графе хотя бы 2 ·(n + 1) = 2n + 2 вершин – противоречие. Тогда
граф связен.


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

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

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