12.2.2. Эйлерова характеристика

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

Теорема (формула Эйлера) В связном планарном графе справедливо следующее:

P - q + r = 2

доказательство

Индукция по q. База: q = 0 => р = 1&г = 1. Пусть теорема верна для всех графов с q ребрами: р - q + г = 2. Добавим еще одно ребро. Если добавляемое ребро соединяет существующие вершины, то q' = q + 1, р' = р, г' = г + 1 и p'-q' + r'=p-q-l + r + l=p — q + r = 2. Если добавляемое ребро соединяет существующую вершину с новой, то р' = р + 1, q' = q + 1, г' = г и р' - q' + г' = =p+l-q-l+r=p-q+r=2 П

СЛЕДСТВИЕ Если G — связный планарный граф (р > 3), то q ^ Зр — 6.

доказательство

Каждая грань ограничена по крайней мере тремя ребрами, каждое ребро ограни­чивает не более двух граней, отсюда 3r ^ 2q. Имеем

2=p-q

q ^ Зр - 6.

у =>• Зр - 3g + 2О 6 :

СЛЕДСТВИЕ К₅ и К₃,з непланарны.

доказательство

Рассмотрим К₅. Имеем р = 5, q = 10. Если К₅ планарен, то по предыдущему следствию q = р(р - 1)/2 = 10 ^ Зр -0 = 3-5-6 = 9 — противоречие.

Рассмотрим К₃,з- Имеем р = 6, q = 9. В этом графе нет треугольников, значит, если этот граф планарен, то в его плоской укладке каждая грань ограничена не менее чем четырьмя ребрами и, следовательно, 4r ^ 2q или 2r ^ q. По формуле Эйлера С - 9 + г = 2, откуда г = 5. Имеем 2r = 2-5 = 10<g = 9- противоречие.

ЗАМЕЧАНИЕ

Граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни Ks, ни Кз,з- Доказательство достаточности этого утверждения выходит за рамки данного курса.

СЛЕДСТВИЕ В любом планарном графе существует вершина, степень которой не больше 5.

доказательство

От противного. Пусть Mv б V d(v) ^ 6. Тогда

6р ^ d(v) = 2q ==> Зр < q,

ОТСТУПЛЕНИЕ

Эйлер вывел свою формулу, исследуя многогранники. Действительно, развертка много­гранника — это плоский граф, и обратно, связному плоскому графу соответствует много­гранник. Таким образом, теория графов имеет связи с самыми разными, на первый взгляд далекими, областями знания.