Задача 31110

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

Сложность: 3+ Классы: 6,7,8

Условие

Доказать, что в двудольном плоском графе  E ≥ 2F,  если  E ≥ 2  (E – число рёбер, F – число областей).

Решение

В двудольном плоском графе каждая область ограничена по меньшей мере четырьмя рёбрами. Поэтому рассуждения, аналогичные решению задачи 30797, приводят к неравенству  E ≥ 2F.

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

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	42