Теорема Понтрягина-Куратовского

Определение:

Граф [math] G_1 [/math] гомеоморфен [math] G_2 [/math] , если [math] G_1 [/math] можно получить из [math] G_2 [/math] с помощью конечного числа применений процедур включения и исключения вершин степени 2.

Теорема:

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math] .

Доказательство:

[math]\triangleright[/math]

Доказательство необходимости можно посмотреть здесь, докажем достаточность. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math]. Пусть [math] G [/math] — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин. G связен Если [math] G [/math] не связен, то его компоненты связности планарны и, следовательно, сам граф [math] G [/math] планарен. G — обыкновенный граф В самом деле, пусть в графе [math] G [/math] есть петля или кратное ребро [math] e [/math]. Тогда граф [math] G - e [/math] планарен. Добавляя ребро [math] e [/math] к графу [math] G - e [/math] получим, что граф [math] G [/math] он планарен. G — блок Пусть, от противного, в графе есть точка сочленения [math] v [/math]. Через [math] G_1 [/math] обозначим подграф графа [math] G [/math], порождённый вершинами одной из компонент связности графа [math] G - v[/math] и вершинной [math] v [/math], а через [math] G_2 [/math] подграф графа [math] G [/math], порождённый вершинами остальных компонент связности графа [math] G - v [/math] и вершиной [math] v [/math]. (рис. 1) рис. 1 Возьмём укладку графа [math] G_1 [/math] на плоскости такую, что вершина [math] v [/math] лежит на границе внешней грани. Ее можно получить, взяв любую укладку [math] G_1 [/math] на плоскости, по ней построив укладку на шаре, используя обратную [http://en.wikipedia.org/wiki/Stereographic_projection

[math]\triangleleft[/math]

Литература

• Асанов М., Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы