Таблицы Брадиса

Тогда выберем в нем какойнибудь

Тогда выберем в нем какойнибудь

Элементы математики в задачах - Г. А. Мерзон

Осталось заметить, что перед тем, как плоскость 2 = с пройдет через последнюю вершину, наш многогранник был или тетраэром, или «косой призмой» — а в этом случае уже нетрудно убедиться в равенстве В+Г — Р = 2.

222                                    Теория графов 2

Задача 32. а) Докажите, что в плоском неориентированном графе

2 Р ^ 3Г.

б) Докажите, что в плоском двудольном неориентированном гра­фе Р ^ 2 Г.

Решение. а) Достаточно заметить, что к каждому ребру примыкает не более двух граней, а к каждой грани — не менее трех ребер, откуда и следует искомое неравенство.

б) Решение аналогично предыдущему случаю, но теперь, посколь­ку граф двудольный, к каждой грани примыкает уже не менее четырех ребер, поэтому оценку можно усилить.

Задача 33. Докажите, что следующие графы не планарны:

а) полный неориентированный граф с 5 вершинами. Этот граф обозначается К5;

б) двудольный неориентированный граф с 3 вершинами в первой доле и 3 вершинами во второй доле, причем каждая вершина первой доли соединена с каждой вершиной второй (такой граф называется полным двудольным). Этот граф обозначается К3,3;

в) произвольный неориентированный граф, у которого степени всех вершин не меньше шести.

Решение. Все три пункта решаются похожим перебором случаев. Мы приведем полное решение для графа К5, для остальных оно будет аналогичным.

Предположим, что граф К5 удалось вложить в плоскость. Тогда вы­берем в нем какой-нибудь гамильтонов цикл и обозначим вершины в нем буквами А, В, С, Б, Е (в порядке следования по циклу).

Вершины А и С соединены ребром. Оно может идти либо внут­ри, либо вне пятиугольника — пока мы без ограничения общности можем считать, что оно идет внутри.