Следствие 2

Графы К₅ и К_{3, 3} – непланарны.

Доказательство

1) К₅ - непланарен.

В этом графе p=5, q=10. Если граф К₅ планарен, то по следствию 1:

Пришли к противоречию.

2) К_{3, 3} – непланарен.

В этом графе p=6, q=9. В К_{3, 3} нет треугольников. Значит, если этот граф планарен, то в его плоской укладке каждая грань ограничена не менее, чем четырьмя ребрами и, следовательно,

или .

По теореме Эйлера

6-9+r=2 находим r=5.

Отсюда 2r=10< =9=q.

Пришли к противоречию.

Следствие 3

В любом планарном графе существует вершина, степень которой не больше 5.

Доказательство

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

,

но, если граф планарен, то . Следовательно, . Пришли к противоречию.