7.2. Формула Эйлера

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

Например, в планарном графе, представленном на рис. 7.4, заштрихованная область бесконечна; — конечные области.

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

Заметим, что всякая область в любой сферической укладке планарного графа конечна.

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

Пусть — области планарного графа, — бесконечная область. Обозначим через цикл на границе области

Рис. 7.4.

Циклы соответствующие конечным областям, называются ячейками.

Легко убедиться в том, что сумма по mod 2 любых ячеек, например есть цикл или объединение реберно-непересекающихся циклов, замыкающих области Так как каждая ячейка замыкает только одну область, никакую из них нельзя получить в результате суммы по mod 2 некоторых других ячеек. Таким образом, ячейки — линейнонезависимы.

Пусть некоторый элемент С подпространства циклов G замыкает конечные области Тогда можно доказать, что . Например, в графе на рис. 7.4 множество ее, замыкает области . Поэтому

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

Теорема 7.3. Ячейки планарного графа G образуют базис подпространства циклов графа

Из этой теоремы непосредственно вытекает следующее следствие:

Следствие 7.3.1 (формула Эйлера). Если связный планарный граф G имеет ребер, вершин и областей, то .

Доказательство. Доказательство следует из теоремы 7.3, если заметить, что цикломатическое число графа G равно

В общем случае трудно проверить, является граф планарным или нет. Используем формулу Эйлера для получения некоторых свойств планарных графов.

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

Следствие 7.3.2. Если связный простой планарный граф G имеет ребер и вершин, то

Доказательство. Пусть — множество областей графа

Пусть степень области означает число ребер на границе мосты считаются дважды. (Например, в графе на рис. 7.4 степень области равна 6.) Заметив аналогию между определениями степени вершины и степени области, получим из теоремы

Так как граф G не содержит ни параллельных ребер, ни петель и 3, то для всех Следовательно, Таким образом, , т.е. . Используя это неравенство в формуле Эйлера, получим или

Следствие 7.3.3. Граф непланарен.

Доказательство. Для . Если бы он был планарным, то по следствию 7.3. получаем противоречие. Таким образом, граф должен быть непланарным.

Следствие 7.3.4. Граф непланарен.

Доказательство. Для Если бы он был планарным, то по формуле Эйлера он имел бы областей.

В графе нет циклов длины менее 4. Следовательно, степень каждой области по крайней мере равна 4. Таким образом, или получим противоречие. Следовательно, граф непланарен.

Следствие 7.3.5. В простом планарном графе G имеется по крайней мере одна вершина степени не более .

Доказательство. Пусть G имеет ребер и вершин. Если каждая вершина имеет степень, превышающую , то по теореме или . Но, согласно следствию . Эти неравенства противоречат друг другу. Следовательно, утверждение следствия верно.