*** Плоские триангуляции ***

Пусть G - связный плоский граф.
Любая грань графа, ограниченная треугольником будет наз-ся треугольником

• Определение №1: ( Плоская триангуляция )
Плоский связный граф, каждая грань которого явл. треугольником наз-ся плоской триангуляцией.

• Определение №2: ( Максимально-плоский граф )
Граф называется максимально-плоским, если после добавления произвольного ребра он перестает быть плоским.

*** Теорема о максимально-плоском графе ***

• Теорема №1:
Граф является максимально-плоским <=> когда он представляет собой плоскую триангуляцию.

-> Док-во:
(Необходимость)
Пусть G - максимально-плоский граф, тогда каждая его грань ограничена либо треугольником либо циклом длины не менее 4.
Рассмотрим грань Г("гамма большая"), ограниченную циклом длины 5.
В графе G одновременно не могут сущ. и ребро (v1,v3) и ребро (v2,v3).
Т.к. оба ребра должны быть вне грани Г, то они обязательно будут пересекаться, что противоречит факту, что G - плоский.
Пусть в G сущ. ребро (v2,v3), и в него добавим ребро (v1,v3), проходящее внутри грани Г.
Тогда согласно свойству 3 (плоских укладок) данное ребро разобьет Г на 2 грани, и полученный граф останется плоским, но тогда G не максимально-плоский граф,
=> все грани графа G - треугольники, а G - плоская триангуляция.
(Достаточность)
Пусть G - плоская триангуляция.
Согласно свойству 3 (плоских укладок) любые 2 в-ны некоторой грани можно соединить ребром, разбивающим грань на 2 грани.
Только в этом случае, когда грани явл. треугольниками это невозможно,
=> граф G - максимально-плоский.

• Следствие №1:
Всякий плоский граф явл. некоторым подграфом плоской триангуляции.

• Следствие №2:
Для любого максимально-плоского графа верно нер-во:
m = 3n - 6.

• Утверждение №1:
Если число вершин некоторой плоской триангуляции не менее 4, то степень каждой в-ны не менее 3-ех.

-> Док-во:
Пусть v - произвольная в-на плоской триангуляции G, и u - плоская ей в-на.
Ребро (u,v) в плоской триангуляции разделяет 2 грани,
=> сущ. x_1 € одной грани и x_2 € другой грани.
Т.О. все в-ны графа G имеют степень не менее 3-ех.

• Утверждение №2:
Всякий планарный граф с числом в-н не менее 4-ех (n >= 4) имеет по крайней мере 4 в-ны, степень которых не превосходит 5.