Если в связном планарном графе , где , , нет циклов длины меньше , то
.
Доказательство. Рассмотрим геометрическую реализацию графа на плоскости. Пусть – число граней и – число сторон, окружающих -ую грань, тогда и , так как каждое ребро разделяет две грани и поэтому учитывается дважды.
и ,
отсюда и , откуда вытекает требуемое неравенство.
Замечание. Если – простой связный планарный граф, то в нем нет циклов длины меньше трех, поэтому
.
Теорема о непланарности графов и .
В графе . Если он планарен, то , то есть – противоречие.
В графе . Если он планарен, то –противоречие.
Определение. Операцией подразбиения ребра называется удаление этого ребра из графа, добавление новой вершины к и
двух новых ребер и к множеству (рис. 26).
Рис. 26 |
Определение. Граф называется подразбиением графа , если он может быть получен из путем конечного числа подразбиений ребер.
Из определения следует, что граф будет отличаться от графа только вершинами степени 2.
Определение. Два графа и называются гомеоморфными, если существуют их подразбиения, которые изоморфны друг другу.
|
|
Пример 9. На рис. 27 изображены гомеоморфные графы.
Рис. 27
Теорема. Понтрягина-Куратовского (без доказательства).
Граф планарен тогда и только тогда, когда не содержит подграфов, гомеоморфных или .
Эта теорема была доказана в 1930 г. советским математиком Львом Семеновичем Понтрягиным и независимо от него польским математиком Казимиром Куратовским, и является критерием планарности графа.
Пример 10. Покажем, что граф, изображенный на рис. 28, непланарен.
Рис. 28 Рис. 29 Рис. 30
Выделим подграф (рис. 29), он гомеоморфен графу (рис. 30).