Олимпиада Туймаада по математике. Старшая лига. 2013 год

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

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

Будем называть раскраску вершин графа правильной если между любыми одноцветными вершинами нету ребра.

Лемма 1: Степень каждой вершины не больше $n$. Тогда вершины можно покрасить в $n+1$ цветов правильным образом.

Док-во:

Отметим все цвета как $[1,2,…,n+1]$. Тогда будем красить следующим образом: Возьмем вершину и покрасим её наименьшим цветом которым не покрашен ни один из её соседей. И так как у вершины не больше $n$ соседей тогда на покраску её и её соседей уйдет макс $n+1$ цветов.

Лемма 2: Если граф не красится правильным образом в $n$ цветов тогда в нем существует связанный подграф в котором степень всех вершин хотя бы $n$.

Док-во:

Пойдем от обратного. Пусть графе нету такого подграфа. Тогда мы будем удалять каждый раз по одной вершине степень которой меньше $n$ (если после одной операции вершина у которой степень была $\geq n$ но стала $<n$ тогда ее тоже удаляем). Тогда так как такого подграфа нету то удалив как только можно вершин у нас от графа останется ничего. И потом продолжая процесс обратно будем по одному заново добавлять по удаленной вершине в этот граф. И из Леммы 1 и так как степень каждой добавленной вершины не больше $n$ тогда мы сможем покрасить граф в $n$ цветов правильным образом.

Перейдем к решению. Из Леммы 2 следует что в графе существует связанный подграф в котором степень всех вершин хотя бы $n$. Тогда докажем что мы можем убрать из этого подграфа $\dfrac{n(n-1)}{2}$ ребер и он все равно останется связанным.

Пусть в этом подграфе $N$ вершин и очевидно что $N \geq n+1$, тогда:

$E-\dfrac{n(n-1)}{2}=\dfrac{\sum d(v_j)}{2} - \dfrac{n(n-1)}{2} \geq \dfrac{Nn}{2}-\dfrac{n(n-1)}{2}$.

Докажем что $\dfrac{Nn}{2} - \dfrac{n(n-1)}{2} \geq N+1$ так как отсюда будет следовать что сделав из этого подграфа дерево, уйдет как минимум $\dfrac{n(n-1)}{2}$ вершин.

$\dfrac{Nn}{2} - \dfrac{n(n-1)}{2} \geq N+1 \Longrightarrow (!) Nn-n^2+n -2N+2 \geq 0 \Longrightarrow Nn-2N-n^2+n+2=N(n-2)-n^2+n+2 \geq (n+1)(n-2)-n^2+n+2=0.\blacksquare$