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

• Теорема №1: ( Формула Эйлера )
Для любого плоского графа имеет место равенство:
    n - m + f = 2
где n - кол-во вершин графа
    m - кол-во ребер графа
    f - кол-во граней графа

-> Док-во:
Пусть дан связный плоский граф G

• Определение №1: ( Остов графа G )
Это подграф графа G с тем же мн-вом вершин, являющийся деревом.

Пусть Т - остов графа G.
Проверим верна ли ф-ла lzk этого остова:
Т имеет n вершин, n-1 ребер, и 1 грань => ф-ла остова Т для р-ва Эйлера верна.
Далее пошагово добавляя отсутствующие ребра будем восстанавливать граф G.
Добавим в Т одно ребро гр. G; полученный граф будет иметь то же кол-во вершин, что и Т, и на 1 больше ребер и граней.
Т.к. m и f в ф-ле имеют противоположные знаки, то ф-ла остается верной и для этого графа.
Т.О. каждый новый шаг процесса восстановления графа G будет порождать графы, для которых ф-ла Эйлера верна.
Процесс заканчивается графом G.

• Следствие №1:
Число граней любой плоской укладки связного планарного графа постоянно и равно:
f = m - n +2

• Следствие №2:
Для любого связного планарного (n,m)-графа, где n ≥ 3, верно нер-во:
m ≤ 3n - 6

-> Док-во:
Не теряя общности р-м произвольный связный плоский (n,m)-граф.
Очевидно, что любое ребро данного графа принадлежит 2-ум граням, исключением явл. дерево с числом в-н как минимум 3, но и в этом случае нер-во выполняется.
Каждая грань (n,m)-графа ограничена как минимум 3-мя ребрами
=> число 3f - это оценка снизу удвоенного числа ребер графа, т.е. 3f ≤ 2m,
т.к. f = m - n +2 (из Сл.№1), то получаем 3m - 3n + 6 ≤ 2m
                                          m ≤ 3n - 6

• Следствие №3:
Граф K_5 не планарен.

-> Док-во:
Предположим, что К_5 - планарный граф. Тогда, согласно Сл.№2, для него должно быть верно нер-во:
m ≤ 3n - 6    (n=5, m=10)
10 не ≤ 3*5-6
=> предположение неверно и К_5 - не планарный граф.


• Следствие №4:
Граф К_3,3 не планарен.

-> Док-во: n=6, m=9
Пусть К_3,3 - планарный граф, тогда каждая его грань ограничена по крайней мере 4-мя ребрами, тогда 4f - нижняя оценка удвоенного числа ребер, т.е. 4f ≤ 2m
Согласно Сл.№1 f=5
Проверим указанное нер-во -> 20 не ≤ 18 => граф К_3,3 не планарен


*** Критерий планарности графов ***

Сущ. несколько формулировок критерия планарности. Р-м один из них:
• Пусть G - некоторый планарный граф и e = (x,y) - произвольное его ребро.
Операция подразбиения ребра e состоит в удалении ребра e из G и добавлением в G 2-ух новых ребер e1 = (x,z) и e2 = (z,y), где z - новая в-на в G.

•Определение: (Гомеоморфные графы)
2 графа называются гомеоморфными если получаются из одного и того же графа подразбиением его ребер.

•Теорема: (Понтрягина - Куратовского)
Граф планарен <=> когда не содержит подграфов, гомеоморфных К_5 и К_3,3