ВсОШ 2022, 9 класс, задача 4

Ответ. .

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

Если граф — это цикл, содержащий вершину, то на любых вершинах ровно рёбер, так что такая компания удовлетворяет условиям задачи. Осталось показать, что не существует такой компании из человек (тогда и компании из более чем человек тоже быть не может). Ниже мы приводим несколько различных способов сделать это; в каждом способе мы предполагаем, от противного, что такая компания нашлась.

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

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

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

С другой стороны, рассмотрим любое ребро . Это ребро учтено в числе ровно тогда, когда вершины и не выброшены в -м способе, то есть когда выброшена какая-то пара из оставшихся вершин. Это происходит в способах. Итак, каждое ребро учтено в чётное количество раз, поэтому должно быть чётным. Противоречие.

Третье решение. Назовём вершину чётной, если её степень чётна, и нечётной иначе. Рассмотрим два случая.

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

Значит, если в графе чётных вершин и нечётных, то чётные вершины имеют (чётную) степень , а нечётные — (нечётную) степень . Это невозможно, ибо .

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

Замечание. Разумеется, существуют и другие примеры компании из человека, удовлетворяющей условию.