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

Ребра полного графа с $n$ вершинами покрашены в несколько цветов таким образом, что каждый цвет встречается не более $n-2$ раз. Докажите, что есть три вершины, все ребра между которыми покрашены в различные цвета.

Подсказка

Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина $A$ , и она соединена ребрами цвета 1 с вершинами $B_{1}, \ldots B_{k}$ . Поскольку $k \leq n-1$ , то остались еще вершины $C_{k+1}, \ldots C_{n-1}$ , каждая из которых соединена с вершиной $A$ ребром какого-то другого цвета.

Решение

Решение 1. Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина $A$ , и она соединена ребрами цвета 1 с вершинами $B_{1}, \ldots B_{k}$ . Поскольку $k \leq n-1$ , то остались еще вершины $C_{k+1}, \ldots C_{n-1}$ , каждая из которых соединена с вершиной $A$ ребром какого-то другого цвета. Рассмотрим вершину $C_{i}$ , пусть она соединена с $A$ ребром цвета $i$ . Тогда $C_{i}$ должна быть соединена с каждой из вершин $B_{1}, \ldots B_{k}$ либо ребром цвета 1 , либо ребром цвета $i$ (иначе будет треугольник с разноцветными сторонами). Если все эти $k$ ребер окрашены в цвет $i$ , то всего из вершины $C_{i}$ выходит $k+1$ ребро цвета $i$ , что противоречит выбору вершины $A$ и цвета 1 . Следовательно, хотя бы одно из этих ребер окрашено в цвет 1. Таким образом, из каждой вершины $C_{k+1}, \ldots C_{n-1}$ выходит хотя бы одно ребро цвета 1 , и всего мы имеем $n-1$ ребро цвета 1 , что противоречит условию. Следовательно, обязательно найдутся три вершины, все три ребра между которыми покрашены в разные цвета.

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