Увидеть граф (переформулировки)

Для построения примера разделяющего множества, в котором не более чем клеток, раскрасим все клетки в три цвета по диагоналям: первую диагональ - в первый цвет, вторую - во второй, третью - в третий, четвертую - опять в первый, и так далее.

Любой цикл из клеток, как легко видеть, пересекает как минимум три соседних диагонали и, следовательно, содержит клетки всех трех цветов. Клеток одного из цветов будет не более , и этот цвет можно использовать в качестве разделяющего множества.

Оценка. Покажем, что никакое не подходит.

Для этого построим граф, вершинами которого являются клетки. Две клетки соединим ребром, если они являются соседними. Получим граф, в котором вершин и ребер, при этом циклы задачи находятся во взаимно однозначном соответствии с циклами в графе. Требуется удалить несколько вершин так, чтобы в оставшемся графе не было циклов.

Предположим, мы удалили вершин. Если в оставшемся графе нет циклов, то этот граф является объединением деревьев и в нем не более чем ребро. При этом из каждой удаленной вершины выходило не более 4 ребер, и всего было удалено было не более ребер. Таким образом, имеем неравенство

откуда

что невозможно при и достаточно большом .