8-ші «Жібек жолы» математикалық олимпиадасы, 2008 жыл

$2n$ төбесі және ${2n(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$ вершине друг от друга.