Лемма о рукопожатиях

Рассмотрим граф, в котором люди — вершины, а сделанные рукопожатия — ребра. Тогда суммарная степень всех вершин равна . При этом по теореме эта сумма должна быть в два раза больше числа ребер. Но сумма нечетна, и такое невозможно, ведь количество ребер не может быть нецелым.

Предположим, что Серёжа добился желаемого. Тогда в графе из условия будет вершин нечетной степени, что противоречит лемме о рукопожатиях.

Рассмотрим граф, каждая вершина — рыцарь либо лжец. Ребро — дружба. По условию из вершин-рыцарей и из вершин-лжецов исходит нечетное количество ребер. Предположим, что в графе 2021 вершина. Получаем противоречие с леммой о рукопожатиях — количество вершин нечетной степени нечетно.

Заметим, что у каждого гостя есть хотя бы по три знакомых интроверта, поэтому интроверты точно есть. Но посмотрим на любого интроверта: у него должно быть хотя бы три знакомых интроверта, но при этом не более трёх знакомых всего (больше у интроверта быть не может). Значит, у каждого интроверта ровно три знакомых, причём все они также интроверты.

Предположим, что на вечеринке есть человек, который не считается интровертов. По условию у него должно быть в друзьях хотя бы три интроверта. Но только что мы показали, что знакомые интроверта обязаны быть интровертами. Значит, предположение неверно. На вечеринке при заданных условиях задачи все должны быть интровертами, а другой ситуации быть не могло.

Осталось привести пример с интровертами. Давайте расположим всех их в вершинах правильного -угольника и проведём его главные диагонали. То есть интроверт в каждой из вершин будет соединён с соседями и противоположной вершиной.

Замечание. Однако при нечётном количестве участников вечеринке пример не удаётся построить, поскольку графа с нечётным количеством вершин нечётной степени не существует по лемме о рукопожатиях.

Рассмотрим полный граф на вершинах, вершинами которого являются джентльмены, а рёбрами — отношения между ними. Покрасим между двумя вершинами в белый цвет, если джентльмены, соответствующие этим вершинам дружат. А чёрные ребра будут символизировать вражду между людьми.

Оценка.

Пусть у джентльмена с номером () ровно друзей и врагов (). Тогда он отправил ровно писем. Это выражение является квадратным трёхчленом, наибольшее значение которого достигается при и равно Тогда число отправленных всеми джентльменами писем не превосходит

Покажем, что отправить ровно писем невозможно по лемме о рукопожатиях (в любом графе количество вершин нечётной степени чётно). Действительно, в таком случае у каждого джентльмена должно быть друзей и врагов. Рассмотрим подграф из всех вершин и только белых рёбер. В этом подграфе количество рёбер (количество пар друзей среди джентльменов) равно половине от суммы степеней вершин (у каждого по друзей, но одну и ту же пару считаем дважды), то есть Противоречие с тем, что это число должно быть целым.

Пример.

Покажем, что отправить писем возможно. Достаточно построить “чёрный” подграф: нужно соединить каждого джентльмена с тремя следующими — получим однородный граф степени затем останется соединить каких-то подряд с джентльменами, которые идут на позиций позже по кругу. То есть Тогда степени первых -и вершин станут равны а у -й она останется равной

Оценка.

Если нашлась вершина (город) степени не больше то она не соединена хотя бы с тремя городами. Возьмём эти три города и саму вершину, получим, что она не может быть в паре ни с одним из них, откуда степень каждой вершины хотя бы Тогда по лемме о рукопожатиях рёбер в графе не меньше

Пример.

Теперь расположим их все в вершинах правильного -угольника(!). Проведём все рёбра графа, кроме сторон самого многоугольника (то есть выкинем рёбер из полного графа). Легко проверить, что степень каждой вершины стала равна Выберем произвольную четвёрку городов и покажем, что она удовлетворяет условию задачи. Нам требуется найти их разбиение на две пары несоседних вершин — тогда внутри пар есть рёбра по построению. Но для этого достаточно соединить их через одну в том порядке, в котором они расположены в -угольнике, тогда вершины в паре разделяет ещё хотя бы одна и соседними они быть не могут.