§ 38. Плоские триангуляции

В этом параграфе изучается особый класс графов — плоские триангуляции. Такие графы интересны тем, что всякий планарный граф порядка n изоморфен подграфу некоторой плоской триангуляции с n вершинами.

Грань плоского графа, ограниченную треугольником (3-циклом), также будем называть треугольником.

Связный плоский граф называется плоской триангу­ляцией, если каждая его грань (в том числе и внешняя) является треугольником. Тем самым, плоская триангуля­ция содержит не менее трех вершин.

Максимальным плоским (планарным) графом назы­вается n-вершинный (n > 3) граф, который перестает быть плоским (планарным) при добавлении любого реб­ра. На рис. 38.1 приведены максимальный и не максимальный плоские графы. Разумеется, что от добавления

кратных ребер планарность графа не нарушается. Однако мы условились рассматривать лишь простые графы.

Теорема 38.1. Граф является максимальным плоским графом тогда и только тогда, когда он представляет собой плоскую триангуляцию.

Необходимость. Пусть G — максимальный плоский граф. Прежде всего заметим, что граф G является 2-связным. Поэтому по теореме 37.7 всякая грань Г такого графа, не являющаяся треугольником, ограничена простым циклом (v₁,v₂,v₃,v₄,...,v₁), содержащим не менее четырех вершин. Так как G — плоский граф, то он

не может одновременно содержатьребра v₁v₃ и v₂v₄ (ведь эти ребра должны быть изображены вне грани Г, см. рис. 38.2). Предположим, например, что v₁v₃  EG. Тогда пос­ле добавления ребра v₁v₃ в грань Г граф G остается плоским, что противоречит его максимальности (рис. 38.2).

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

Теорема 38.1 дает следующее важное

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

Иными словами, каждый плоский граф можно допол­нить ребрами так, что он станет плоской триангуляцией.

Из теоремы 38.1 и следствия 37.6 (при m= 3) вы­текает

Следствие 38.3. Для всякого максимального планарного (n, т)-графа т = 3n — 6.

Утверждение 38.4. Если число вершин плоской триангуляции не меньше четырех, то степень каждой вершины не менее трех.

Возьмем произвольную вершину v. Пусть w — смежная с ней вершина. Ребро vw принадлежит двум гра­ням — треугольникам (v, w, u₁) и (v, w, u₂), причем u₁  u₂, так как число вершин графа не меньше четырех Таким образом, v смежна по крайней мере с тремя вер­шинами w,u₁,u₂

Утверждение 38.5. Всякий планарный граф с n  4 вершинами имеет по крайней мере 4 вершины со степенями, не превосходящими 5.

Без потери общности будем считать граф G плос­ким. Добавляя ребра, сделаем граф G максимальным плоским графом G', каждая вершина которого в силу утверждения 38.4 имеет степень не меньше 3. Поэтому,, принимая во внимание следствие 38.3 и лемму о рукопо­жатиях (утверждение 5.1), получаем

где n — число вершин графа G', m — число его ребер, а n_i — число вершин степени i в этом графе. Отсюда, учи­тывая, что n =Σ n_i,i>2, легко получаем

i  3

n₃ + n₄ +n₅  4 т. е. в графе G', а тем более в графе G, имеется по край­ней мере 4 вершины со степенями, не превышающими 5.