Изменения
Нет описания правки
Граф [[Укладка_графа_на_плоскости| планарен]] тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex> .
|proof =
Возьмем укладку графа <tex> G_1 </tex>. Добавив на нужных ребрах вершины степени <tex> 2 </tex> и удалив некотрые вершины степени <tex> 2 </tex> в старом графе , получим укладку гомеоморфного графа <tex> G_2 </tex>, следовательно . Следовательно из планарности графа следует планарность гомеморфного графа и наоборот.
От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>.
Если <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> оказалась на внешней грани стереографической проекции повернутого шара.
