Теорема Эйлера о плоском графе

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

Теорема 11. Пусть G (V, E, F) — связный плоский геометрический граф, имеющий / V / =v вершин, 1е 1=е ребер и IfI=f граней. Тогда имеет место следующее равенство (формула Эйлера для плоского графа):

Доказател ьство. Рассмотрим три способа доказательства этой важной теоремы.

I способ (индукция по количеству граней f). База индукции очевидна, так как если / =1, то G не имеет циклов, т. е. является деревом, и для него v — е = 1. Следовательно, v-e + / = 1 + 1 = 2. Пусть формула (2.3.1) справедлива при / = к. Рассмотрим граф с к+1 гранью. Удалим в этом графе произвольное ребро, примыкающее к двум различным граням. В результате число. вершин останется неизменным, число ребер уменьшится на 1, число граней уменьшится на 1 (две грани сольются в одну), и величина v — e + f не изменится. Но при / = к по предположению индукции v — е + / = 2, следовательно, формула (2.3.1) справедлива для любого количества граней.

II способ (выделение покрывающего дерева). Будем удалять ребра в плоском графе до тех пор, пока не получим суграфа, являющегося покрывающим деревом. Каждое удаление ребра будет уменьшать количества граней и ребер на единицу, а величина v — ё + f будет оставаться неизменной. Следовательно, эта величина будет одинаковой как у исходного графа, так и у его покрывающего дерева. Но у дерева v — е + f = 2.

III способ (полная разборка графа). Легко видеть, что следующие операции разборки (или сборки) графа не меняют величины v — е + f.

• • удаление ребра, разделяющего две грани (добавление ребра между вершинами, лежащими на границе грани);
• • удаление висячей вершины вместе с инцидентным ей ребром (добавление ребра с висячей вершиной).

Очевидно, при помощи этих операций разборки любой плоский связный граф можно свести к нуль-графу, т. е. графу, состоящему из одной изолированной вершины (при помощи описанных операций сборки любой связный плоский граф можно собрать из нуль-графа). Но для нульграфа v=f=l, e = 0 и v — е + / = 2. Следовательно, формула (2.3.1) справедлива для любого связного плоского графа.

Следствие 1. Для любого связного сферического графа справедлива формула Эйлера (2.3.1).

Действительно, при помощи стереографической проекции любой связный сферический граф отображается на связный плоский граф, для которого выполняется равенство (2.3.1).

Следствие 2. Для любого простого многогранника' справедлива формула Эйлера (2.3.1).

Для доказательства этого факта можно либо применить один из способов доказательства теоремы 11, либо деформировать поверхность многогранника в сферу (например — «раздуть») и применить формулу Эйлера для полученного сферического графа. Заметим, что формула Эйлера позволяет получить ряд интересных свойств многогранников. В частности, с ее помощью мы докажем, что существует ровно 5 типов правильных многогранников.