О плоских правильных графах

Квант 1975, №11 с. 12-15 Тег 85P8

М. Г. Кац

Начнем с определений.
Графом называем конечное множество точек и соединяющих их кривых на плоскости (эти точки будем называть вершинами, а кривы — ребрами).
Будем рассматривать графы, обладающие следующим свойствами:

ребра графа не пересекаются (графы, обладающие этим свойством, называются плоскими);
никакие две вершины не соединены более чем одним ребром;
любые две вершины графа соединены звеном ребер (такой граф называется связным);
каждое ребро соединяет две разные вершины.

Если разрезать плоскость по ребрам графа, то она распадется на несколько частей — граней графа. Неограниченно часть будем называть внешней граью. Остальные грани — внутренние.

Грань называется $n$ -реберной, если число ребер, встречающихся при обходе грани вдоль границ, равно $n$ . Пример. На рисунке 1,a грань всего одна — внешняя шестипереберная, на рисунке 1,6 — две грани: внутренняя трехпереберная и внешняя трехпереберная.

Ребро называется внешним (соответственно внутренним), если при обходе внутренних граней графа оно встречается соответственно один или два раза. Пример. На рисунке 2 ребро $a$ — внешнее, ребро $b$ — внутреннее; на рисунке 1,a нет ни внешних, ни внутренних ребер.

Обозначим через $B$ , $P$ и $\Gamma$ соответственно число вершин, ребер и всех граней графа, включая внешнюю. Эти три величины связаны известной формулой Эйлера $^*$

$B - P + \Gamma = 2.$

Обозначим через $a_i$ число $i$ -реберных граней, включая и внешнюю. Тогда справедливо такое соотношение:

$2P = 3a_3 + 4a_4 + 5a_5 + \dots$

Докажите это самостояльно.

Поскольку $\Gamma = a_3 + a_4 + \dots$ , то соответствие (1) можно записать в виде

$2P = 3\Gamma + a_4 + 2a_5 + \dots,$

или

$\Gamma = \frac{2}{3}P - \frac{1}{3}(a_4 + 2a_5 + \dots).$

Подставив это значение $\Gamma$ в формулу Эйлера, получим

$B - P + \frac{2}{3}P - \frac{1}{3}(a_4 + 2a_5 + \dots) = 2,$

*) См. «Квант», 1974, № 8.

$3B - P = 6 + \sum_{i=1}^{i+3} i a_{i+3}.$

Назовем степенью $\deg V_i$ вершины $V_i$ число ребер, выходящих из этой вершины. Так как каждое ребро соединяет две вершины, то $\sum_{i=1}^{i+3} \deg V_i = 2P$ .

Введем величины $\deg V$ , называемую средней степенью графа:

$\deg V = \frac{\sum_{i=1}^{i+3} \deg V_i}{B}.$

Из определения вытекает, что $\sum_{i=1}^{i+3} \deg V_i = B \deg V$ , то есть $2P = B \cdot \deg V$ , откуда $P = \frac{1}{2} B \cdot \deg V$ .

Подставив это выражение для $P$ в формулу (2), получим

$3B - \frac{1}{2} B \cdot \deg V = 6 + \sum_{i=1}^{i+3} i a_{i+3},$

или

$B \cdot (6 - \deg V) = 12 + 2 \sum_{i=1}^{i+3} i a_{i+3}.$

Таким образом, средняя степень графа всегда меньше 6, но она может быть сколько угодно близка к 6 — доказите это.

Назовем граф $n$ -угольник, если из каждой его вершины выходит одинаковое число ребер. Очевидно, что средняя степень правильного графа равна числу ребер, выходящих из каждой вершины (будем назвать ее просто степенью правильного графа).

Из формулы (3) вытекает

Теорема 1. Степень правильного графа не превозходит 5.

Нибольное интересный тип правильных графов — это графы степени 5. Посмотрим, сколько вершин может иметь правильный граф степени 5.

Очевидно (см. формулу (3)), что меньше 12 вершин у правильного графа такой степени быть не может. Правильный граф с 12 вершинами действительное существует и представляется собой проекцию икосаэдра на плоскость (рис. 3). Из четности же произведения $B \cdot \deg V = 2P$ получаем, что графов степени 5 с нечетным числом вершин не существует.

Сейчас мы опишем способ построения правильных графов с любым четыREM числом вершин (не меншим 12), кроме графов с 14, 18 и 22 вершинами. О графах с 14 и 18 вершинами см. замещение в конце статы; граф с 22 вершинами изображен на рисунке 4.

Возьем выпуклый $n$ -угольник $A = (A_1, A_2, \dots, A_n)$ . Внутри него помещим $n$ -угольник $B = (B_1, B_2, \dots, B_n)$ . Соединив середины соседних сторон $n$ -угольника $B$ , получим $n$ -угольник $C = (C_1, C_2, \dots, C_n)$ , где $C_i$ — середина $B_i B_{i+1}$ , $i = 1, 2, \dots, n-1$ ; $C_n$ — середина $B_n B_1$ .

Рис. 3.

Рис. 4.

Рис. 5.

Соединив середины соединих сторон $n$ -угольника $C$ , получим $n$ -угольник $D = (D_1, \dots, D_n)$ , где $D_i$ — середина $C_{i-1}C_i$ , $i = 2, \dots, n$ ; $D_1$ — середина стороны $C_nC_1$ . Соединив теперь $A_i$ с $B_i$ , $B_{i+1}$ и $C_i$ , а $B_i$ — с $D_i$ , получим граф степени 5 с $4n$ вершинами. Пример построения графа с 20 вершинами (для $n = 5$ ) избражен на рисунке 5.

Покажем теперь как к уже построениюу графу с $4n$ вершинами можно добавить еще 2 вершины.

Уберем одно из внешних ребер графа с $4n$ вершинами. Телерь в графе есть две вершины, из которых выходит по 4 ребра — на рисунке 6 это вершины $A$ и $B$ . Выберем точку на несоседнем ребре—точку $C$ , и соединим ее с вершинами $A$ и $B$ . К вершинам исходного графа добавилась вершина $C$ , из которого выходит 4 ребра. Уберем еще одно внешнее ребро и аналогично построим точку $C'$ . Соединив точку $C$ с точкой $C'$ , получим новый граф степени 5, у которого уже на 2 вершины больше, чем у исходного (см. рис. 6).

Заметим, что описанное добавление двух вершин к графу с $4n$ вершинами возможно лишь в том случае, когда у исходного графа не меньше шести внешних ребер (позмоту-то наша конструкция и не дает способа построения для графов с 14, 18 и 22 вершинами).

Итак, доказана.

Теорема 2. Число вершин правильного графа степени 5 можно быть

две неконцевые точки любых двух несовпадающих ребер этой грани. Тем самым теорема 3 для графов степени 3 доказана.

2°. Графы степени 4. Из формулы (3) получаем, что у правильного графа степени 4 не менее шести вершин. Граф с шестю вершинами изображен на рисунке 7. Из формулы (3) также следует, что у графа степени 4 с числом вершин, строго большим 6, всегда имеет нетрехреберная грань. Отбросим (см. рис. 8) ребро AB этой грани и соединим вершины A и B с любой точкой на неоседнем с ребром AB ребре (таксе ребро найдется, поскольку выбирается нетрехреберная грань). Тем самым к исходному графу с числом вершин, строго большим 6, добавлена одна вершина (пример построения — на рисунке 8). Базисом индекции может служить граф с 8 вершинами, изображенный на рисунке 9.

Итак, мы доказали, что существует графы степени 4 с 6 вершинами и с любым числом вершин, не меньше 8.

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

Рассмотрим произвольную вершину A изходного графа и вершины A₁, A₂, A₃, A₄, с которых она соединина. Оставшиеся две вершины нашей

Рис. 9. Рис. 10.

го графа обозначим через A’ и A’’. Возможны два случая.

1°. Вершины A’ и A’’ не соединены между собой.

Тогда, для того чтобы из A’ и A’’ выходило по четыре ребра, они должны быть соединены со всеми четырьмя вершинами A₁, …, A₄ (из вершины A уже выходят четыре ребра. В таком случае искомый подграф выбрать легко: в качестве вершин I II, III (см. рис. 10) можно взять вершины A, A’ и A’’, а в качестве вершин IV, V, VI — вершины A₁, A₂, A₃.

2°. Вершины A’ и A’’ соединины между собой.

В этом случае из вершин A’ и A’’ выходит еще по три ребра к некоторым из вершин A₁, …, A₄. Поэтому хотя бы две из вершин A₁, …, A₄ соединены и с A’, и с A’’. Пусть это вершины A₁ и A₂. Расстоянием снова два случая.

Одна из вершины A₃ и A₄ соединина и с A’, и с A’’. В таком случае искомый подграф — это подграф с вершинами A, A’, A’’, A₁, A₂, A₃.
A₃ и A₄ соедининыровно с одной из вершин A’ и A’’ какдая, скажем A₃ с A’, а A₄ с A’’. Отбросим ребро AA₄ и заменим два ребра A₃A₄*) и A₄A’’ одним ребром A₃A’’’. Искомый подграф получен — это подграф с вершинами A, A’, A’’, A₁, A₂, A₃.

Заметание. Из формул (3) и (1) следует, что правильный граф степени 5 с 14 вершинами должен иметь лишь один четырьмя ребрами и 22 трехреберника. Непредседательным перебором можно убедиться, что такого графа не существует.

Для графа степени 5 с 18 вершинами имеются три возможности:

3 четырьмя ребрами, 26 трехреберников;
1 пятиеберник, 1 четырьмя ребром, 27 трехреберников;
1 шестиеберник, 28 трехреберников.

В этом случае не предусмотрены перебор затруднительен, и вопрос о существовании правильного графа степени 5 с 18 вершинами пока остается открытым.

*) Ребро A₃A₄, оченьindo, должно существовать.