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