2.2    Теорема Л.Эйлера о плоских графахискомое равенство является верным.

Если С содержит ребро вида

где р(а) = 1, то удаляя из С вершину а и это ребро, мы докажем искомое равенство в силу предположения индукции. Итак, можно считать, что С - плоский связный граф, в котором степень каждой вершины > 2 и среди ребер нет петель (и кратных ребер).

Лемма. Если степень каждой вершины графа С\ не меньше двух, то С\ содержит цикл.

ДОКАЗАТЕЛЬСТВО. Если в С\ есть петли или кратные ребра, то лем­ма доказана. Иначе, 6?1 - простой граф. Пусть у £ У{С\). Пусть у\ -смежная вершина с у,у2 - смежная вершина с у\ и отличная от и,из -смежная вершина с у 2 и отличная от у\ и т.д. Так как < оо, то в по­следовательности у,У1,У2, ■ ■ ■ встретится вершина ук, которая встречалась раньше. Выбирая к минимальным с этим свойством, мы получим искомый цикл.

Следовательно граф С содержит цикл. Удалим в этом цикле одно ребро. Полученный граф является снова связным, но число его ребер р\ = р — 1 и число его граней Т\ = г — 1. Ввиду предположения индукции р\ + 2 = Ь\ +г\. Следовательно, р + 2 = Ь + г и теорема доказана.

Если мы рассмотрим выпуклый многогранник в И/3) и спроектируем его на поверхности сферы, описанной около него, а затем воспользуемся сте­реографической проекцией, то мы получим плоский связный граф много­гранника, для которого справедлива формула Эйлера

р + 2 = Ъ + г.

Следствие 1. Если С = (У, Е) - связный простой планарный граф порядка п = |У| > 3 и размера т = \Е\, то т < Згг — 6.

ДОКАЗАТЕЛЬСТВО. Подсчитывая ребра в графе, имеем Зг < 2га. Сле­довательно,

2

т+2=п+г<п+ -га,       га < 3(гг — 2).

3

Следствие 2. Б любом простом планарном графе существует верши­на, степень которой не превосходит 5.

ДОКАЗАТЕЛЬСТВО.Для доказательства достаточно считать, что граф является связным. Если степень каждой вершины > 6, то 6 • п < 2га, где п - число всех вершин и га - число всех ребер. Откуда следует, что Згг < га < Згг — 6. Противоречие.

Следствие 3. Пусть Є - плоский граф порядка п, с га ребрами, г гра­нями и к компонентами связности. Тогда п + г = т+(к+1).

Доказательство следует из теоремы и того, что бесконечная грань счи­тается только один раз.

Задача 10. Пусть Є = (V. Е) - план арный граф порядка п > 3, в котором все циклы содержат > д > 3 ребер. Доказать, что число ребер

га = \Е\ < тахЦп — 1), -—-—г(п — 2)}.

УКАЗАНИЕ. Можно считать, что с/ < п и О связный граф. Если в О каждое ребро принадлежит двум граням, то

2т = ^2/і-і>^2/і-і> д(^2 /*) = 9 ' >■

і і>д і

где г - число всех граней is.fi - число граней с г ребрами на своих границах. Следовательно,

2

га + 2 = гг + г<ггН—га,

га < —-—(п — 2).

Если ребро {а, 6} Є Е принадлежит одной грани, то Є\{а, 6} - объединение двух непересекающихся графов Є\   и Сг- Полагая ті = \Е(С{)\, щ = | О і |. / < 2, имеем, чтога = гаї + гаг + 1 < тах{-^{п\ — 2),п\ — 1}+ +гааж{^2(?і2 — 2),     — 1} + 1 < тах{-^[п — 2), п — 1}.

В частности, если бы граф К5 был бы плоским, то у = 3. г;(Я5) = 10 < | • (5 - 2). Противоречие.