Индукция в графах и теорема Турана
Ошибка.
Попробуйте повторить позже
В графе степень каждой вершины не меньше 
Доказать, что его можно разбить на 
части так, чтобы любая вершина была соединена с
какой-то из другой части.
Подсказка 1
Попробуйте доказать задачу для связного графа, отсюда будет следовать и для несвязного. Почему это так?
Подсказка 2
Задачу стоит решать по индукции. Подумайте, какой факт про связные графы поможет доказать переход?
Подсказка 3
У любого связного графа можно выкинуть некоторую вершину без потери связности. Именно этот факт вам поможет.
Будем доказывать по индукции для связного графа. Если граф не связный, разобьём его на компоненту связности и решим задачу отдельно для каждой компоненты связности.
Итак, для графа на 
вершине утверждение очевидно. Рассмотрим граф на 
вершинах. Выкинем из него вершину 
так,
чтобы оставшийся граф был связным. Полученный граф по предположению можно разбить на две части так как нужно.
Теперь вернем вершину 
Она обязательно соединена с какой-то вершиной 
Добавим 
в часть, в которой нет
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
