Задача 30805

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

Сложность: 4+ Классы: 9,10

Условие

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

Решение

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

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	13
Название	Графы-2
Тема	Теория графов
задача
Номер	027