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