12. Плоские укладки графов, планарные графы, критерий Понтрягина-Куратовского.

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

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

Определение. Изображение графа на плоскости без внутренних точек пересечения ребер называется плоской укладкой графа.

Определение. Граф называется планарным, если существует его плоская укладка.

Утверждение 1 (необходимое условие планарности). Для любого связного планарного графа с n вершинами и m ребрами, где n ≥ 3, выполняется неравенство .

Утверждение 2 (необходимое условие планарности). В любом планарном графе есть вершина, степень которой не превосходит пяти.