- Попробуй найти соответствие между количеством ребер и областей.
Заметим, что каждое ребро ограничивает (входит в) максимум две области и
каждая область ограничена хотя бы 3 ребрами.
Спойлер
Тогда 2Е будет не меньше количества областей, при этом, каждая область посчитается столько раз, сколько ребер ее ограничивает (как минимум 3). Поэтому,
2E \ge 3F
- Из определения плоских двудольных графов выходит, что каждая область ограничена хотя бы 4 ребрами (должно быть четное количество, 3 не подходит).
Спойлер
Поэтому, в предыдущем неравенстве 3 заменяется на 4:
2E \ge 4F
3 лайка
Подсказки по 5 и 6.
Для плоского связного графа справедливо что E \leq 3 V - 6 (почему?). Попробуй из данного утверждения вывести противоречие к задаче 5 и 6.
2 лайка