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