Утверждение: Полный граф K₅ – не планарен.

Доказательство: допустим противное – граф K5 планарен и G есть его плоская укладка. Т.к. граф K5 и G изоморфны, то каждое ребро G есть 3-цикл. Положим n=3, p=5, q=10, получаем 10 ≤ 3*(5-2) / (3-2) = 9 ⇒ что противоречит условию ⇒ граф K₅ – не планарен.

Утверждение: Граф K_3,3 – не планарен.

Доказательство: допустим противное: граф K_3,3 – планарен и имеет плоское изображение G, т.к. K_3,3 и G изоморфны, то каждая грань в G есть 4-цикл. Подставляем в формулу следующие значения n=4, p=6, q=9, получаем 9 ≤ 4(6-2) / (4-2) = 8 ⇒ противоречие ⇒ K_3,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 тоже.

Утверждение: Каждый планарный граф G (p,q) имеет вершину степени S ≤ 5.

Доказательство: Допустим противное – все вершины планарного (p,q) графа G имеют степени S ≥ 6. Т.к любая вершина графа G имеет степень вершины S ≥ 6, а каждое ребро соединяет две вершины, то в G число ребер q ≥ 6*p/2 = 3p и потому q = 3*p +k для некоторого k ≥ 0. Подставляя это значения в неравенство q ≤ 3p – 6 получаем, 0 ≤ k ≤ -6 – противоречие, ⇒ Планарный (p,q) граф G имеет вершину степени S ≤ 5.

Критерий Понтрягина-Куратовского

Вершину степени 2 в графе назовем проходной. Операция добавления проходной вершины в ребро e=(u,v) в графе G = (V,E), состоит в удалении ребра е из Е и добавлении к V новой вершины w и в добавлении в граф G двух ребер (u,w) и (w,v). Операция удаления проходной вершины v в графе G=(V,E) есть удаление вершины v из V и замена двух е-инцидентных в Е ребер e’ = (u,v) и e’’=(v,w) на одно ребро e = (u,w).

Операция стягивания ребра e = (u,v) в графе G=(V,E) в точку состоит в удалении ребра е из Е и в объединении (склеивании) принадлежащих е вершин в одну вершину.

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

Замечание: Если графы геоморфны, то они планарны или непланарны одновременно.

Теорема Понтрягина — Куратовского: Граф G – планарен ⇔ G не содержит подграфов гемеоморфных графам K₅ или K_3,3.

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