5.10. Следствия из формулы Эйлера для плоских графов

Следствие 1. Пусть G – связный плоский (p,q,m)-граф без петель и кратных ребер. Тогда q3p–6.

Доказательство. Пусть g_i – некоторая грань графа G. Обозначим через (g_i) число ребер, ограничивающих грань g_i. (g_i)3, так как нет петель и кратных ребер. Тогда (m – число граней в графе G), так как каждое ребро ограничивает 2 грани, (g_i)3. Следовательно, 3m2q. По формуле Эйлера p+m = q+2, т.е. m = q+2–p, то 3(q+2–p) 2qq3p–6.

Следствие 2. Граф K₅ не планарен.

Доказательство. Предположим, что граф K₅ планарен, тогда существует плоский граф G такой, что .

Так как полный граф без петель и кратных ребер, то по следствию 1 т.е. 1035–6 = 9. Получаем противоречие, значит, граф K₅ – не планарен.

Следствие 3. Граф K_3,3 не планарен.

Доказательство. Пусть граф K_3,3 планарен, т.е. , где G – плоский граф и p(G) = 6, q(G) = 9. Пусть граф G имеет m граней: g₁, …,g_m. – это следует из того, что в графе нет треугольников, т.е. нет цикла из 3 ребер. Значит, из вершины в нее саму мы можем попасть лишь за четное число шагов. Рассмотрим , но . Но, так как граф G плоский, то справедлива формула Эйлера: p+m = q+2m = q+2–p.

.

Получаем противоречие, значит, граф K_3,3 не планарен.

Следствие 4. В любом плоском связном графе G без петель и кратных ребер существует вершина , степень которой не больше 5, т.е. .

Доказательство. Как известно, . Предположим, что для , где . Тогда , т.е. , . В силу следствия 1 q3p–6, пришли к противоречию. Значит, существует вершина, что .

5.11. Операция подразделения ребра

Пусть дан граф G=(V,E). Пусть ребро e=(v,w) – произвольное ребро графа G и .

Операция подразделения ребра e=(v,w) графа G состоит в построении графа ,имеющего своими вершинами множество ,содержащего все ребра графа G, кроме выделенного e=(v,w), и плюс два новых ребра e=(v,v), e=(v,w), т.е. .

Определение. Граф H называется подразделением графа G, если он может быть получен из графа G путем применения конечного числа раз операций подразделения ребра.

5.12. Гомеоморфность графов

Определение. Графы G и H называются гомеоморфными, если существуют такие их подразделения, которые изоморфны.

Пример:

Из данного примера видно, что графы G и H не изоморфны, т.е.

• , ^{но графы G и H гомеоморфны, так как каждый из них может быть подразделен до графа Г.}

5.13. Теорема Понтрягина-Куратовского

Теорема 3 (Понтрягина-Куратовского). Для того чтобы граф G был планарным, необходимо и достаточно, чтобы он не содержал ни одного подграфа, гомеоморфного графам или.

Доказательство.

1) Необходимость. Пусть G – планарный. Допустим, что он содержит подграф , гомеоморфный графуили. Рассмотрим планарную реализацию графаG. Удалив лишние вершины и рёбра, мы получим планарную реализацию подграфа . Ногеометрически – это графилис точками на рёбрах. Если проигнорировать эти точки, то мы получим планарную реализацию графаили. Но это невозможно по следствиям 2 и 3.

2) Достаточность доказывается тяжело, и здесь мы это доказательство опустим. Доказательство можно найти, например, в книге Ф. Харари «Теория графов» (под ред Г.П. Гаврилова. М. : Изд-во «Мир», 1973).