VII математическая олимпиада «Шелковый путь», 2008 год

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

Комментарий/решение

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

Случай 1. Два черных ребра имеют общую вершину. Тогда исключим из графа эту вершину, и еще по одной вершины из которых выходят оставшиеся черные ребра. Итого мы исключили не более $n-2+1=n-1$ вершин. Тогда останется полный граф на $n+1$ вершине и полностью покрасив его в красный цвет, мы решим задачу.

Случай 2. Никакие два черных ребра не имеют общую вершину. Тогда у нас есть $n$ пар вершин, где в паре ребра черного цвета. Расставим все вершины в вершины правильного $2n$угольника.

Если $n$ - четное. То сделаем так чтобы черные ребра были большие диагонали. Покрасим в красный цвет все вершины и все ребра соединяющие вершины которые находятся не более чем в $\frac{n}{2} - 1$ вершине друг от друга.

Если $n$ - нечетное. Сделаем так что черные ребра составляли стороны нашего многоугольника через одну. Тогда покрасим в красный цвет все вершины и все ребра соединяющие вершины которые находятся не более чем в $\frac{n + 1}{2} - 1$ вершине друг от друга.