Упражнения

7.1. Покажите, что если G — связный планарный граф с ребрами, вершинами и обхватом то Используя этот результат, докажите, что граф Петерсена непланарный.

7.2. Докажите, что простой планарный графе 4 вершинами имеет по крайней мере четыре вершины степени 5 или меньше.

7.3. Докажите или опровергните: любой связный простой непланарный граф стягивается к или .

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

7.5. Используя теорему Куратовского, докажите, что граф Петерсена непланарный.

7.6. Найдите два неизоморфных графа, двойственных к графу на рис. 7.12.

7.7. Докажите, что планарный граф без петель неразделим тогда и только тогда, когда неразделим двойственный к нему граф.

7.8. Покажите, что двойственный граф к неразделимому планарному графу эйлеров тогда и только тогда, когда граф двудольный.

7.9. Планарный граф является самодвойственным, если он изоморфен двойственному к нему графу. Покажите, что если граф G на вершинах и ребрах самодвойственный, то

7.10. Графом с одной терминальной парой называется граф, две вершины которого помечены как терминальные. Планарным графом с одной терминальной парой называется граф с одной терминальной парой, являющийся планарным и остающийся им после введения ребра, которое соединяет терминальные вершины.

Рис. 7.12.

Параллельно-последовательным графом является граф с одной терминальной парой, определяемый рекурсивно:

а) отдельное ребро (с концевыми вершинами) есть параллельно-последовательный граф. Если G и G" — параллельно-последовательные графы, то

б) последовательная комбинация графов G и G" есть параллельно-последовательный граф. Под последовательной комбинацией графов G и G" мы понимаем соединение одной из терминальных вершин [рафа G с одной из терминальных вершин графа G" (рис. 7.13, а).

Рис. 7.13. а — последовательная комбинация графов б — параллельная комбинация графов

в) Параллельная комбинация графов G и G" есть параллельно-последовательный граф. Под параллельной комбинацией этих графов мы понимаем соединение двух терминальных вершин графа G с двумя терминальными вершинами графа G" (рис. 7.13, б). Покажите, что граф, двойственный к графу G, является параллельно-последовательным тогда и только гогда, когда граф G — параллельно-последовательный.