Задача 083 — Задачи на Графы

Степени всех вершин графа $G$ меньше $\frac{3 n}{2}-1$ (где $n>2$ ), причем среди любых $n+1$ вершин есть две несмежных. Назовем блоком множество из $n$ попарно смежных вершин графа $G$ . Известно, что любые два блока имеют общую вершину. Докажите, что все блоки имеют общую вершину.

Подсказка

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

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

Решение

Доказательство. Пусть утверждение леммы неверно. Будем считать $n$ наименьшим натуральным числом, для которого существует граф, не удовлетворяющий условию задачи. Рассмотрим граф $H$ , дополнительный к графу из условия. Рассмотрим любой пустой подграф графа $H$ с $n$ вершинами, множество его вершин обозначим через $X$ , а множество остальных вершин через $Y$ . Назовем подмножество $Y$ плохим, если количество вершин в нем больше количества вершин в $X$ , смежных хотя бы с одной вершиной из этого подмножества. Обозначим через $A$ максимальное плохое подмножество (оно может быть и пустым), пусть оно содержит $k$ вершин, тогда в $Y A$ нет плохих подмножеств, поэтому, в силу леммы Холла, каждой вершине $Y A$ можно сопоставить смежную с ней вершину $X$ таким образом, чтобы все эти вершины были различны и не смежны с вершинами из Y $\backslash$ A. Множество не сопоставленных вершин $X$ обозначим через $B$ . Рассмотрим граф $H^{\prime}$ , образованный вершинами $A \cup B$ и ребрами графа $H$ , соединяющими эти вершины. Заметим, что при выкидывании любой вершины $H^{\prime}$ в графе $H$ должен был найтись пустой подграф с $n$ вершинами, но в него могло входить не более, чем $n-k-1$ вершина из ( $X \cup Y$ ) $\backslash(A \cup B)$ , следовательно, остальные $k+1$ вершин должны быть из $A \cup B$ , поэтому в $H^{\prime}$ после выкидывания любой вершины найдется пустой подграф с $k+1$ вершинами, но тогда, в силу минимальности $n$ либо в $H^{\prime}$ найдется пустой подграф с $k+2$ вершинами, либо $k=n$ . В первом случае, добавляя к вершинам этого подграфа вершины из $X \backslash B$ , получим пустой подграф с $n+1$ вершинами, во втором — выкинем вершину из $X$ , несмежную ни с одной вершиной $Y$ , найдем пустой подграф $H$ с $n$ вершинами и добавим к нему эту вершину, получим пустой подграф $H$ с $n+1$ вершинами. Полученное противоречие доказывает утверждение леммы.

Обозначим через $k$ разность максимальной степени графа и $n$ . Из условия следует, что $2 k+2 \leq n$ .

Доказательство. Пусть $T$ — объединение всех блоков, содержащих $L$ . Тогда $|T| \leq n+k+1$ , поскольку любая вершина из $L$ смежна с любой вершиной из $T$ . Ясно, что любой блок, содержащий $L$ , имеет не менее $n-|L|$ вершин в $T L L$ . Пусть $|L|<n-k-1$ . Заметим, что при выкидывании любой вершины из $T L$ найдется блок, содержащий $L$ , но не содержащий выкинутой вершины (поскольку $L$ — пересечение всех блоков, содержащих $L$ ). Но в $T \backslash L$ нет подграфов, содержащих более $n-|L|$ вершин (иначе объединение такого подграфа с $L$ будет полным подграфом графа $G$ , содержащим более $n$ вершин). Тогда $T L$ содержит не менее $2(n-|L|)$ вершин в силу леммы 1 . Следовательно, $2(n-|L|) \leq|\mathrm{T} \backslash \mathrm{L}| \leq n+k+1-|L|$ , откуда $|L| \geq n-k-1$ . Лемма доказана.

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