COM-B2-M07-P017 Планарная оценка

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

Пусть \(f\) — число граней. По формуле Эйлера \(n-m+f=2\). Так как граф простой и \(n\ge3\), каждая грань ограничена не менее чем тремя рёбрами. При суммировании длин границ граней каждое ребро считается дважды, значит, \(3f\le2m\).

Тогда \(f\le\frac{2m}{3}\), и \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Отсюда \(m\le3n-6\).

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