Планарные графы. Формула Эйлера

Задача 00009

от

Какое наибольшее число клеток доски 9×9 можно разрезать по обеим диагоналям, чтобы при этом доска не распалась на несколько частей?

Решение

Пусть разрезано k клеток. Рассмотрим граф, рёбрами которого являются половинки проведённых диагоналей, а вершинами – вершины и центры разрезанных клеток.
Поскольку граничные клетки доски, очевидно, разрезать нельзя, то в полученном графе не более 64 + k вершин и 4k рёбер. Согласно формуле Эйлера (64 + k) – 4k + 1 ≥ 2, то есть k ≤ 21.
Пример с 21 разрезанной клеткой см. на рисунке.

Задача 00008

от

Семиугольник разбит на выпуклые пяти- и шестиугольники, причём так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

Решение

Рассмотрим полученную картинку как плоский граф. Так как из каждой вершины выходит не менее трёх рёбер, то  E ≥ 3V/2.  Подставив в формулу Эйлера, получим  2 = V – E + F ≤ 2E/3 – E + F = F – E/3,  то есть  E ≤ 3F – 6.
  Обозначим количество пятиугольников через a, количество шестиугольников через b. Заметим, что  5a + 6b + 7 = 2E ≤ 6F – 12 = 6(a + b + 1) – 12.  Отсюда  a ≥ 13.