Verified answer

Предположим обратное: у всех плоских графов степень вершин не меньше 6. Тогда, по лемме о рукопожатиях,

С другой стороны, для любого плоского графа справедливо неравенство

Тогда - противоречие.

А значит предположение неверно.

А значит в любом плоском графе найдется вершина, степень которой не превосходит 5.

Ч.т.д.

___________________________

- мн-во ребер графа, - мн-во вершин, - мощность мн-ва (т.е. кол-во элементов этого множества), - степень вершины

___________________________

Док-во неравенства

Обозначим через множество граней связного плоского графа.

Очевидно, что каждая грань задается не менее чем двумя ребрами. При этом каждое ребро входит не более чем в 2 грани. Тогда

По формуле Эйлера , тогда, подставив полученное неравенство, имеем

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

Ч.т.д.

Предположим обратное: из каждой вершины выходит по крайней мере 6 ребер. Тогда достаточно доказать, что эйлерова х-ка не равна 2. То есть не выполняется равенство ;

Итак, из каждого ребра выходит по крайней мере 6 ребер. Значит, всего ребер не менее, чем ;

Пусть - количество ребер i-ой грани. Тогда , но ; Значит, ;

Теперь запишем так:

;

Итого: , что и требовалось.