Изменения
Нет описания правки
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex>, и не содержит подграфов, гомеоморфных <tex> K_{3, 3} </tex> .
|proof =
=== [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%BF%D0%BB%D0%B0%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C_K5_%D0%B8_K3,3 Необходимость ] ===Необходимость условия очевидна.
=== Достаточность ===
От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Пусть <tex> G </tex> — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.
