Подсчёты в графах

Лемма 1. (В.Л. Дольников). В графе вершин. Оказалось, что после выкидывания любой вершины графа найдется полный подграф с вершинами. Тогда в исходном графе найдется полный подграф с вершиной.

Лемма 2. Пусть — пересечение нескольких блоков графа , причем непусто. Тогда содержит не менее вершин.

Лемма 1. (В.Л. Дольников). В графе вершин. Оказалось, что после выкидывания любой вершины графа найдется полный подграф с вершинами. Тогда в исходном графе найдется полный подграф с вершиной.

Доказательство. Пусть утверждение леммы неверно. Будем считать наименьшим натуральным числом, для которого существует граф, не удовлетворяющий условию задачи. Рассмотрим граф , дополнительный к графу из условия. Рассмотрим любой пустой подграф графа с вершинами, множество его вершин обозначим через , а множество остальных вершин через . Назовем подмножество плохим, если количество вершин в нем больше количества вершин в , смежных хотя бы с одной вершиной из этого подмножества. Обозначим через максимальное плохое подмножество (оно может быть и пустым), пусть оно содержит вершин, тогда в нет плохих подмножеств, поэтому, в силу леммы Холла, каждой вершине можно сопоставить смежную с ней вершину таким образом, чтобы все эти вершины были различны и не смежны с вершинами из Y A. Множество не сопоставленных вершин обозначим через . Рассмотрим граф , образованный вершинами и ребрами графа , соединяющими эти вершины. Заметим, что при выкидывании любой вершины в графе должен был найтись пустой подграф с вершинами, но в него могло входить не более, чем вершина из ( ) , следовательно, остальные вершин должны быть из , поэтому в после выкидывания любой вершины найдется пустой подграф с вершинами, но тогда, в силу минимальности либо в найдется пустой подграф с вершинами, либо . В первом случае, добавляя к вершинам этого подграфа вершины из , получим пустой подграф с вершинами, во втором — выкинем вершину из , несмежную ни с одной вершиной , найдем пустой подграф с вершинами и добавим к нему эту вершину, получим пустой подграф с вершинами. Полученное противоречие доказывает утверждение леммы.

Обозначим через разность максимальной степени графа и . Из условия следует, что .

Лемма 2. Пусть — пересечение нескольких блоков графа , причем непусто. Тогда содержит не менее вершин.

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

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

Рассмотрим любую группу из 51 человека. Если выкинуть любого из них, среди оставшихся будет одно и то же число знакомств. Поэтому в этой группе каждый имеет среди остальных 50 одно и то же число знакомых.

Ответ: .

Решение. Рассмотрим любую группу из 51 человека. Если выкинуть любого из них, среди оставшихся будет одно и то же число знакомств. Поэтому в этой группе каждый имеет среди остальных 50 одно и то же число знакомых. Пусть оно равно . Тогда общее число знакомств среди 50 человек должно равняться . Значит, значение а будет одним и тем же для всех компаний из 51 человека. Возьмем любого человека Ч. Среди остальных 99 есть либо 50 знакомых с ним, либо 50 незнакомых с ним. Добавляя их к Ч, получим компанию, где в первом случае , а во втором . Но второй случай невозможен по условию, а в первом случае, очевидно, каждый знаком с каждым. Отсюда получаем ответ.

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет.

Если в графе знакомств есть треугольник, то из остальных 17 вершин не выходят ребра. Пусть треугольников нет. Заметим, что каждая компонента связности графа знакомств содержит не более 4 вершин (иначе там есть пять вершин, связанные минимум 4 ребрами). Такие компоненты могут иметь вид одиночного ребра, цепи из двух или трех ребер и «»ежа»» из трех ребер, исходящих из одной вершины. Легко проверить, что в каждой такой компоненте можно отметить не менее половины вершин так, чтобы никакие две отмеченные вершины не были связаны ребром. Сделав это, получим не менее 10 отмеченных вершин, попарно не соединенных между собой.

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

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

Пусть . Всего у 20 ребер 40 концов и легко понять, что есть не менее 12 ребер, концы которых не совпадают с другими концами наших 20 ребер. Выберем 5 таких ребер — пусть это ребра . Обозначим через множество, состоящие из вершин и произвольных 40 вершин не входящих в . Применим операцию ко всем 50 вершинам множества . Тогда на каждом из ребер образуется по 30 треугольников (со всеми вершинами, не входящими в ), а на каждом из 15 оставшихся ребер — по 50 треугольников (со всеми вершинами множества ). Итого получается треугольников.