Изменения

Пусть граф <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 \geqslant 4</tex>. Получаем <tex>4F \leqslant 2E</tex>, то есть <tex>2F \leqslant E</tex>. То есть <tex>2\cdot5 = 10 \leqslant 9</tex>, что невозможно.

}}

==Источники информации==

* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. {{---}} СПб.: Издательство "Лань", 2010. {{---}} C. 134 {{---}} (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2

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

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