Формула Л. Эйлера, 1758 г.

Для всякого связного плоского графа верно равенство

n – m + f = 2. (5.1)

¨ Пусть G – связный плоский n -вершинный граф. Рассмотрим некоторый остов T этого графа. Очевидно, что дерево T имеет одну грань (внешнюю) и n вершин. В то же время известно, что число ребер дерева T равно n – 1. Поэтому для графа T формула (5.1) верна. Теперь будем поочередно добавлять к T недостающие ребра графа G. При этом на каждом шаге число вершин, естественно, не меняется, а число ребер и число граней увеличивается на единицу на основании свойства 5.5. Следовательно, формула (5.1) будет верна для всякого графа, получающегося в результате таких операций (шагов), а поэтому она верна и для графа G, которым заканчивается вся эта процедура. ¨

Из теоремы Эйлера вытекает ряд интересных следствий. Прежде всего, рассмотрим в трехмерном пространстве выпуклый многогранник с n вершинами, m ребрами и f гранями. Очевидно, что спроектировав этот многогранник на описанную около него сферу, далее уложив его так, чтобы северный полюс находился внутри одной из граней, и, произведя затем стереографическую проекцию, получим связный плоский граф. Поэтому справедливо следующее следствие.

Следствие 5.7. У всякого выпуклого многогранника сумма числа вершин n и числа граней f без числа ребер m равна двум: n – m + f = 2.

Доказательство именно этой формулы и было впервые опубликовано Л. Эйлером в 1758 г. в «Записках Петербургской академии наук».

Следствие 5.8. Число граней любой плоской укладки связного планарного (n, m)-графа постоянно и равно m – n + 2.

Другими словами, число f является инвариантом планарного (n, m)-графа, т.е. не зависит от способа укладки этого графа на плоскости.

Следствие 5.9. Для связного планарного (n, m) -графа m £3 n – 6 при n ³ 3.

¨ Не теряя общности, будем считать, что G – плоский граф. Прежде всего заметим, что всякое ребро плоского графа либо разделяет две различные грани, либо является мостом (см. свойство 5.6). Поскольку G – граф без петель и кратных ребер, то всякая грань ограничена, по крайней мере, тремя ребрами (исключение составляет лишь случай, когда G – дерево с тремя вершинами, но для такого графа неравенство m £ 3n – 6очевидно). Поэтому число 3 f является оценкой снизу удвоенного числа ребер графа G, т.е. 3 f £ 2. Отсюда, учитывая формулу Эйлера
f = m – n + 2, получаем требуемое неравенство. ¨

Равенство в указанном следствии достигается на плоских связных графах, в которых каждая грань, в том числе и внешняя, является треугольной (другие названия треугольной грани – треугольник, 3-грань). Такие графы называются плоскими триангуляциями.

Следствие 5.10. Для всякой плоской (n, m)- триангуляции, m =3 n – 6.

Из следствия 5.9 сразу же получаем утверждение 5.11.

Утверждение 5.11. Граф K ₅ не планарен.

¨ Действительно, для полного графа K ₅ имеем n = 5, m = 10. Поэтому неравенство 3 n – 6 ³ m превращается в неверное: 9 > 10, т.е. граф K ₅ не может быть планарным. ¨

Утверждение 5.12. Граф K _{3, 3} не планарен.

¨ Для рассматриваемого графа n = 6, m = 9. Поэтому, если бы он был планарным, то для любой его плоской укладки выполнялось бы f = 5 согласно следствию 5.8. В то же время всякая грань двудольного графа K _{3, 3} должна быть ограничена, по меньшей мере, четырьмя ребрами. Следовательно, 2 m ³ 4 f, т.е. 18 > 20. Противоречие. ¨

Как мы увидим далее, графы K ₅ и K _{3, 3} являются минимальными непланарными графами и играют важную роль во многих критериях планарности.

Дата добавления: 2015-07-08