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