COM-B2-M07-P019 Планарный двудольный граф

В двудольном графе нет треугольников, значит, каждая грань имеет длину хотя бы \(4\).

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

Сумма длин границ граней равна \(2m\), значит, \(4f\le2m\), то есть \(f\le\frac{m}{2}\). Тогда \(2=n-m+f\le n-m+\frac{m}{2}=n-\frac{m}{2}\). Отсюда \(m\le2n-4\).

Сильная планарная оценка, часто используемая для запрета \(K_{3,3}\).