Теорема о связи числа ребер с длиной минимального цикла

Если в связном планарном графе , где , , нет циклов длины меньше , то

Доказательство. Рассмотрим геометрическую реализацию графа на плоскости. Пусть – число граней и – число сторон, окружающих -ую грань, тогда и , так как каждое ребро разделяет две грани и поэтому учитывается дважды.

и ,

отсюда и , откуда вытекает требуемое неравенство.

Замечание. Если – простой связный планарный граф, то в нем нет циклов длины меньше трех, поэтому

Теорема о непланарности графов и .

В графе . Если он планарен, то , то есть – противоречие.

В графе . Если он планарен, то –противоречие.

Определение. Операцией подразбиения ребра называется удаление этого ребра из графа, добавление новой вершины к и

двух новых ребер и к множеству (рис. 26).

Рис. 26

Определение. Граф называется подразбиением графа , если он может быть получен из путем конечного числа подразбиений ребер.

Из определения следует, что граф будет отличаться от графа только вершинами степени 2.

Определение. Два графа и называются гомеоморфными, если существуют их подразбиения, которые изоморфны друг другу.

Пример 9. На рис. 27 изображены гомеоморфные графы.

Рис. 27

Теорема. Понтрягина-Куратовского (без доказательства).

Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных или .

Эта теорема была доказана в 1930 г. советским математиком Львом Семеновичем Понтрягиным и независимо от него польским математиком Казимиром Куратовским, и является критерием планарности графа.

Пример 10. Покажем, что граф, изображенный на рис. 28, непланарен.