Дан связный планарный граф без петель и кратных рёбер с $V$ вершинами, $E$ рёбрами и $F$ гранями, где обхват (длина наименьшего цикла) равен 5. Докажите, что $E \leq \frac{5}{3}(V-2)$.
Правильный ответ
Каждая грань ограничена не менее 5 рёбрами (обхват 5), каждое ребро смежно с не более чем 2 гранями: $5F \leq 2E$. По формуле Эйлера $F = 2 - V + E$, поэтому $5(2-V+E) \leq 2E$, откуда $10 - 5V + 5E \leq 2E$, $3E \leq 5V - 10 = 5(V-2)$, то есть $E \leq \frac{5}{3}(V-2)$.
💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!