Кубок Колмогорова

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

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

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

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

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

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

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

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

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

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

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