Как решить эти задачи(графы)? Прошу подсказки

image
image

  1. Попробуй найти соответствие между количеством ребер и областей.

Заметим, что каждое ребро ограничивает (входит в) максимум две области и

каждая область ограничена хотя бы 3 ребрами.

Спойлер

Тогда 2Е будет не меньше количества областей, при этом, каждая область посчитается столько раз, сколько ребер ее ограничивает (как минимум 3). Поэтому,
2E \ge 3F

  1. Из определения плоских двудольных графов выходит, что каждая область ограничена хотя бы 4 ребрами (должно быть четное количество, 3 не подходит).
Спойлер

Поэтому, в предыдущем неравенстве 3 заменяется на 4:
2E \ge 4F

3 симпатии

Подсказки по 5 и 6.

Для плоского связного графа справедливо что E \leq 3 V - 6 (почему?). Попробуй из данного утверждения вывести противоречие к задаче 5 и 6.

2 симпатии
© 2021 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)