Формула Эйлера

Для связного плоского графа справедливо следующее соотношение между количеством вершин , ребер и граней (включая внешнюю грань):

Оно было найдено Эйлером в 1736 г.^[1] при изучении свойств выпуклых многогранников. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это инвариант поверхности, для плоскости или сферы он равен двум, а, например, для тора — нулю.

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

следовательно,

то есть, при большем числе рёбер такой граф заведомо непланарен. Обратное утверждение не верно: в качестве контрпримера можно взять граф Петерсена. Отсюда следует, что в планарном графе всегда можно найти вершину степени не более 5.

Общая формула также легко обобщается на случай несвязного графа:

где — количество компонент связности в графе.

Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.

Определение: Граф G есть максимальный планарный (плоский) граф, если G планарный, то при прибавлении к G любого ребра, он перестает быть планарным (плоским)

Замечание: Любая грань максимального плоского (p,q) – графа, есть 3-цикл (треугольник). Подставляя в формулу следствия n=3, получим q ≤ 3*(p-2)/(3-2) = 3*p – 6, т.е. для максимального плоского (p,q) — графа G число ребер q ≤ 3p – 6. Тогда для немаксимального плоского (p,q) графа G (который получается удалением некоторых ребер из некоторого максимального графа) число ребер q ≤ 3*p – 6 тем более. Т.к. планарный граф изоморфен некоторому плоскому графу, то для планарного (p,q) графа G число ребер q ≤ 3p – 6 тоже.