Изменения
→Разбор случаев взаимного положения a, b, c, d, u1, u2, v1, v2
{{Теорема
|statement =
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex>, и не содержит подграфов, гомеоморфных <tex> K_{3, 3} </tex> .
|proof =
=== Необходимость ===
Необходимость условия очевидна.
=== Достаточность ===
От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Пусть <tex> G </tex> - такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.
==== G связен ====
Если <tex> G </tex> не связен, то его компоненты связности планарны и, следовательно, сам граф <tex> G </tex> планарен.
==== G - обыкновенный граф ====
В самом деле, пусть в графе <tex> G </tex> есть петля или кратное ребро <tex> e </tex>. Тогда граф <tex> G - e </tex> планарен. Добавляя ребро <tex> e </tex> к графу <tex> G - e </tex> получим, что граф <tex> G </tex> он планарен.
==== G - блок ====
Пусть, от противного, в графе есть точка сочленения <tex> v </tex>. Через <tex> G_1 </tex> обозначим подграф графа <tex> G </tex>, порождённый вершинами одной из компонент связности графа <tex> G - v</tex> и вершинной <tex> v </tex>, а через
<tex> G_2 </tex> подграф графа <tex> G </tex>, порождённый вершинами остальных компонент связности графа <tex> G - v </tex> и вершиной <tex> v </tex>. (рис. 1)
==== Разбор случаев взаимного положения ''a, b, c, d, u1, u2, v1, v2'' ====
Рассмотрим 2 случая.
Таким образом, доказано, что в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br>
}}
==Литература==
