Формула Эйлера: в любом связном плоском графе числа p,q,r его вершин, ребер, граней соответственно связаны равенством Эйлера (p-q+r=2)

Доказательство: Индукцией по числу q ребер.
Базис: q=0 ⇒ p – q + r = 1 – 0 + 1 = 2
Предположение индукции: Допустим, что формула Эйлера справедлива для всех связных плоских графов с числом ребер < q. Шаг индукции: Покажем, что формула Эйлера справедлива для всех связных плоских графов с числом ребер q, пусть плоский граф G имеет p вершин, q ребер, r граней, возможны следующие 2 случая. 1) Граф G имеет простой цикл, удалим из G циклическое ребро e, граф G’ = G – e связен, имеет p – вершин, q-1 ребер, r-1 граней, то по предположению индукции для графа G’ формула Эйлера справедлива и тогда p – (q - 1) + (r - 1) =2 ⇒ p-q+r =2 2) Связный граф G простых циклов не имеет, тогда граф G есть дерево с единственной внешней гранью. Все ребра в G ацикличны. Удалим из G любое ребро e и получим несвязный граф G’=G-e c двумя компонентами связности G1 и G2 и числами (p₁, q₁, r₁), (p₂, q₂, r₂) вершин, ребер и граней. Т.к. q₁,q₂ < q, то по предположению индукции для графов G1, G2 формула Эйлера справедлива: p₁ – q₁ + 1 = 2, p₂ – q₂ + 1 = 2 ⇒ (p₁ + p₂) – (q₁ + q₂) + (1 + 1) = 4 ⇒ p — (q₁ + q₂ +1) +1 = 2 ⇒ p –q +1 =2 ⇒ p – q +r =2
Шаг индукции установлен, Теорема доказана.

Следствие: Если G есть связный плоский (p,q) — граф, каждая внутренняя грань в G есть n-цикл (простой цикл длины n), то q ≤ (n*(p-2)) / (n-2)

Доказательство: Т.к. каждая внутренняя грань в G имеет n ребер, внешняя грань в G имеет тоже n ребер и любое ребро в G принадлежит двум граням, то n*r ≤ 2*q, ибо каждое ребро слева входит дважды, тогда r ≤ 2*q / n, то по формуле Эйлера (p — q +2*q / n) ≥ 2 ⇒ q ≤ (n*(p-2)) / (n-2).

Комментарии запрещены.