2. Число вершин малых степеней в плоском графе.

Утверждение 13.14. Если число вершин плоской триангуляции не меньше четырех, то степень каждой вершины не менее трех.

 Возьмем произвольную вершину v. Пусть w — смежная с ней вершина. Ребро vw принадлежит двум граням-треугольникам (v, w, u₁) и (v, w, u₂), причем u₁  u₂, так как число вершин графа не меньше четырех. Таким образом, v смежна по крайней мере с тремя вершинами w, u₁, u₂. 

Утверждение 13.15. Всякий планарный граф с n  4 вершинами имеет по крайней мере 4 вершины со степенями, не превосходящими 5.

 Без потери общности будем считать граф G плоским. Добавляя ребра, сделаем граф G максимальным плоским графом G‘, каждая вершина которого в силу утверждения 13.12 имеет степень не меньше 3. Поэтому, принимая во внимание следствие 13.12 и лемму о рукопожатиях, получаем

2(3n –6) = 2m = 3n₃ + 4n₄ + 5n₅ + …  3(n₃ + n₄ + n₅) + 6(n₆ + n₇ + n₈ + …) ,

где n — число вершин графа G‘, m — число его ребер, а n_i — число вершин степени i в этом графе. Отсюда, учитывая, что n = n₃ + n₄ + n₅ + … , легко получаем n₃ + n₄ + n₅  4 т. е. в графе G‘, а тем более в графе G, имеется по крайней мере 4 вершины со степенями, не превышающими 5. 