Следствие 3

Граф K₅ – непланарен. m > 2

И если бы он был плоским, то для него было бы справедливо следствие 1: n £ 3(m–2).

10 £ 9 – неверно. Противоречие. Значит, он не может быть нарисован плоским.

Следствие 4: Граф K_3,3 непланарен.

Нет треугольных граней. Если бы он был плоским, то для него было бы справедливо следствие 2: 9 £ 2*(6–2). 9 £ 8 – неверно. Противоречие из предположения, что он не может быть плоским.

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

Операцией разбиения ребра графа (добавления вершины в ребро) называется следующая процедура: ребро удаляется из графа, и в граф добавляется новая вершина, соединенная новыми ребрами с концами данного ребра.

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

Теорема Понтрягина – Куратовского.

Чтобы граф был планарным, необходимо и достаточно, чтобы он не содержал подграфов, гомеоморфных К₅ и К_3,3.

Дополнение.

Теория перечисления графов занимается разработкой методов подсчёта числа неизоморфных графов, обладающих тем или иным свойством. Решены задачи о числе графов, орграфов, связных графов, эйлеровых графов и деревьев, содержащих данное число вершин и рёбер. Однако соответствующие результаты для планарных и гамильтоновых графов не получены

Лекция 13

Задачи и алгоритмы на графах. Циклы и разрезы