ВсОШ 2022, региональный этап, 11 класс, задача 4
В компании некоторые пары людей дружат (если дружит с , то и дружит с ). Оказалось, что при любом выборе человека из этой компании количество пар дружащих людей среди них нечётно. Найдите наибольшее возможное количество человек в такой компании.
(Е. Бакаев, И. Богданов)
Ответ
Ответ. .
Решение. Во всех решениях ниже мы рассматриваем граф дружб, в котором вершины — это люди в компании, а два человека соединены ребром, если они дружат.
Рассмотрим вершины, и построим на них следующий граф. Одну вершину соединим с тремя другими . Остальные вершин разобьём на пары и соединим вершины в каждой паре. Получился граф с рёбрами. При удалении любой вершины удаляется нечётное число рёбер, то есть остаётся также нечётное число. Поэтому компания, описанная в условии, может состоять из человек.
Осталось показать, что не существует такой компании из человек (тогда и компании из более чем человек тоже быть не может). Ниже мы приводим несколько различных способов сделать это; в каждом способе мы предполагаем, от противного, что такая компания нашлась.
Первое решение. Существует всего способа выбросить две вершины из , оставив . Пронумеруем эти способы числами от до . Пусть — количество рёбер на оставшихся вершинах в -м способе; по предположению, все числа нечётны, а значит, нечётна и их сумма (поскольку число нечётно).
С другой стороны, рассмотрим любое ребро . Это ребро учтено в числе ровно тогда, когда вершины и не выброшены в -м способе, то есть когда выброшена какая-то пара из оставшихся вершин. Это происходит в способах. Итак, каждое ребро учтено в чётное количество раз, поэтому должно быть чётным. Противоречие.
Второе решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.
Случай 1. Пусть общее количество рёбер в графе нечётно. Тогда, выкидывая любую пару вершин, мы должны выкинуть из графа чётное число рёбер (чтобы осталось нечётное число). С другой стороны, если мы выкидываем вершины со степенями и , то число выкинутых рёбер равно , если эти вершины не соединены ребром, и , если соединены. Отсюда следует, что вершины одинаковой чётности всегда не соединены ребром, а вершины разной чётности — всегда соединены.
Значит, если в графе чётных вершин, то общее число рёбер равно , то есть чётно. Но мы предполагали, что это количество нечётно — противоречие.
Случай 2. Пусть общее количество рёбер в графе чётно. Аналогично получаем, что вершины одинаковой чётности всегда соединены ребром, а вершины разной чётности не соединены. Поэтому, если в графе чётных вершин, то число отсутствующих рёбер равно , то есть чётно. Поэтому общее число рёбер есть , то есть нечётно. Но мы предполагали, что это количество чётно.
Замечание 1. Разумеется, существуют и другие примеры компании из человек, удовлетворяющей условию.
Замечание 2. Существует и такая вариация второго решения.
Рассмотрим произвольные вершины и индуцированный подграф на этих вершинах, пусть в нём рёбер. Выбрасывая из них произвольную вершину (скажем, степени ), получаем вершину с нечётным количеством рёбер . Значит, степень любой вершины в нашем подграфе имеет чётность, отличную от чётности , то есть степени всех вершин имеют одну и ту же чётность.
Рассмотрим теперь весь граф на вершинах. Назовём вершину чётной, если после её удаления остаётся граф, в котором все степени вершин чётны, и нечётной иначе. Тогда две вершины одной чётности соединены с одними и теми же из остальных вершин, а две вершины разной чётности — с наборами вершин, дополняющими друг друга до всего множества из оставшейся вершины. Отсюда несложно выяснить, как и во втором решении, что граф — либо полный двудольный, либо объединение двух полных графов. Далее можно действовать как и в этом решении.