дискретная-математика - Доказать, что любой планарный связный граф, на n<=11 вершинах, является 4-раскрашиваемым

Прежде всего, надо заметить, что в графе не должно быть петель и кратных рёбер, то есть это подразумевается в условии. Далее, граф можно считать связным, рассуждая относительно каждой его связной компоненты. В силу планарности, граф можно уложить без самопересечений на сфере, и для этой укладки будет выполнена формула Эйлера: В-Р+Г=2.

Если предположить, что степень каждой вершины не меньше 5, то отсюда следует неравенство 5В<=2Р (поскольку удвоенное число рёбер равно сумме степеней вершин). Далее, каждая грань содержит не менее трёх рёбер, откуда следует неравенство 3Г<=2Р (с учётом того, что ребро находится на границе двух граней). Таким образом, 2=В-Р+Г<=В-Р/3<=В-5В/6=В/6, и оказывается, что В>=12, вопреки условию.

Теперь, с учётом доказанного утверждения, 4-раскрашиваемость доказывается индукцией по числу вершин (примерно так же, как в известной теореме Хивуда). Берём произвольную вершину степени <=4, удаляя её из графа вместе с инцидентными рёбрами. То, что осталось, раскрашиваем в 4 цвета. Если степень удалённой вершины меньше 4, или если она равна 4, но среди её соседей какой-то цвет отсутствует, то для этой вершины найдётся подходящий цвет. Осталось рассмотреть случай, когда соседей 4, и все их цвета -- разные.

Рассмотрим картинку на плоскости: вершина v (пока не раскрашенная) имеет соседей v1, v2, v3, v4, и соединена с ними рёбрами e1, e2, e3, e4, идущими по часовой стрелке. Цвета этих вершин равны 1, 2, 3, 4 соответственно. Рассмотрим подграф раскрашенного графа, состоящий из вершин цветов 1 и 3, а также соединяющих их рёбер. Если вершины v1, v3 лежат в разных связных компонентах этого графа, то перекрасим цвета вершин компоненты, которой принадлежит v1, меняя местами цвета 1 и 3. Тогда v1 будет иметь цвет 3, и v раскрасим в цвет 1. Если же обе эти вершины лежат в одной компоненте, то они соединены путём p, в котором цвета 1 и 3 чередуются.

Теперь то же самое сделаем для вершин v2 и v4. Там тоже или возможна раскраска, или v2 соединена с v4 путём q, в котором цвета 2 и 4 чередуются. Из топологических соображений понятно, что такое невозможно. Действительно, путь p вместе с рёбрами e1, e3 образует цикл, разделяющий вершины v2, v4. Поэтому q пересечёт этот цикл в какой-то вершине, что невозможно, так как в цикле никакие вершины не имеют ни цвета 2, ни цвета 4.