Упражнения

9.1. Доказать или опровергнуть: любое вершинное покрытие содержит минимальное вершинное покрытие.

9.2. Даны целые Пусть — такое целое число, что

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

Если G — простой граф на вершинах и ребрах с то

9.3. Покажите, что если G — простой граф на вершинах с ребрами, то

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

9.5. Получите теорему Холла 8.13 из теоремы 9.2.

9.6. Получите теорему Холла 8.13 из теоремы 9.5.

9.7. Покажите, что

9.8. Покажите, что для графа G без петель где к — максимальное число параллельных ребер между любыми двумя вершинами графа G [9.4].

9.9. Пусть G — граф без петель. Покажите, что если Д то или 4.

9.10. Покажите, что для однородного непустого графа с нечетным числом вершин

9.11. Покажите, что для произвольной ориентации ребер простого графа G существует ориентированный путь длиной

9.12. Покажите, что если два любых цикла нечетной длины графа имеют общую вершину, то

9.13. Покажите, используя следствие 7.3.5, что любой планарный граф -раскрашиваемый.

9.14. Покажите, что если простой граф G имеет последовательность степеней то

9.15. Покажите, что для простого графа G на вершинах

9.16. Пусть G — простой однородный граф степени k на вершинах. Покажите что

Рис. 9.9.

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

9.18. Покажите, что простой граф непланарен, если он имеет семь вершин и степень каждой вершины равна 4 [9.24].

9.19. а) Покажите, что граф -раскрашиваемый тогда и только тогда, когда все его циклы имеют четную длину.

б) Покажите, что области планарного графа G можно правильно раскрасить в два цвета тогда и только тогда, когда граф G — эйлеров.

9.20. Найти хроматический полином графа, представленного на рис. 9.9.

9.21. а) Покажите, что граф G на вершинах является деревом тогда и только тогда, когда

б) Покажите, что если на вершинах связный, тогда

9.22. Покажите, что если G — цикл длины , то

9.23. Покажите, что если G — колесо на вершинах, то

9.24. Покажите, что если простой граф G имеет вершин, ребер и k компонент, то

а) коэффициент при в Р-полиноме равен

б) наименьший показатель степени Я, в полиноме с ненулевым коэффициентом равен к.

9.25. Клика графа есть такое множество что порожденный подграф G на S является полным графом. Пусть — разбиение множества V на клики. Пусть

Таким образом, есть наименьшее возможное число клик, на которые можно разбить множество V.

Покажите, что для простого графа G существует неравенство Кроме того, покажите, что если S — независимое множество, такое разбиение множества V на клики, что то -максимальное независимое множество, минимальное разбиение V на клики,