Изменения
Нет описания правки
{{Теорема
|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> его компоненты связности планарны и, следовательно, сам граф <tex> G </tex> планарен.
=== G — обыкновенный граф ===
В самом деле, пусть в графе <tex> G </tex> есть петля или кратное ребро <tex> e </tex>. Тогда Тогдаd в силу минимальности <tex> G </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) В силу минимальности <tex> G </tex>,<tex> G_1 </tex> и <tex> G_2 </tex> - планарны.
[[Файл:New.p-k.1.png|thumb|right|рис. 1]]
Возьмём укладку графа <tex> G_1 </tex> на плоскости такую, что вершина <tex> v </tex> лежит на границе внешней грани. Ее можно получить, взяв любую укладку <tex> G_1 </tex> на плоскости, по ней построив укладку на шаре, используя обратную [http://en.wikipedia.org/wiki/Stereographic_projection стереографическую проекцию], потом повернуть сферу так, чтоб <tex> v </tex> оказалась на внешней грани стереографической проекции повернутого шара.
[[Файл:New.p-k.3.png|thumb|right|рис. 3]]
Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно.
=== В G нет мостов === Граф <tex> G <br/tex> не равен <tex> K_2 </tex> и в нем нет точек сочленения, следовательно в <tex> G <br/tex>нет [[Мост,_эквивалентные_определения|мостов]].
=== В G' существует цикл, содержащий вершины a и b ===
Пусть <tex> e = ab </tex> — произвольное ребро графа <tex> G </tex>, <tex> G' = G - e </tex>.
