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