Изменения

Пусть граф <tex>K_{3,3}</tex> планарен. Тогда по [[Формула Эйлера|формуле Эйлера]] <tex>F = E - V + 2 = 9 - 6 + 2 = 5</tex>. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum_{i=1}^{F}l_i = 2E</tex>. Поскольку граф двудольный, все его циклы имеют четную длину. Значит <tex>l_i \ge 4</tex>. Получаем <tex>4F \le 2E</tex>, то есть <tex>2F \le E</tex>. То есть <tex>2\cdot5 = 10 \le 9</tex>, что невозможно.

}}

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Укладки графов ]]