УПРАЖНЕНИЯ. 1. При каких значениях графы Gn (определение см

1. При каких значениях графы G_n (определение см. в упр. 14
гл. I) планарны?

2. Докажите, что любой граф можно уложить в трехмерном
пространстве так, что все его ребра будут изображены прямоли­-
нейными отрезками.

3. Всегда ли планарен реберный граф L(G) планарного гра-­
фа G?

4. Нарисуйте граф, изоморфный графу, изображенному на
рис. 37.1, так, чтобы внешней стала грань а) 2; б) 3.

5. Скольким граням может принадлежать вершина степени
d ³ 1 плоского графа?

6. Покажите, что формула Эйлера следующим образом обоб­-
щается на случай несвязного плоского графа: n — m +f =k+ 1,
где k — число связных компонент графа, а остальные символы
имеют прежний смысл.

7. Нарисуйте плоский граф (n>5), среди вершин которого
ровно 4 вершины со степенями, не превышающими 5.

8. Существуют ли 6-связпые планарные графы?

9. Докажите, что для связного плоского (n,m)-графа с n ³ 3,
грани которого не являются треугольниками, верно неравенство
n£2n— 4.

10. Покажите, что всякая плоская триангуляция с n ³ 3 вер-
шинами имеет 2п — 4 грани.

11. Все вершины плоской триангуляции раскрашены произ-
вольным образом в три цвета. Грань будем называть правильной,

если ее вершины окрашены в три различных цвета. Покажите, что число правильных граней четно.

12. Пусть в плоской триангуляции G существуют такие три
вершины а, b, с, что граф G—{а, b, с} не является связным. До-
кажите, что тогда граф G содержит 3-цикл (а, b, с), не являющий-
cя границей грани.

13. Для всякого связного планарного (n, m)-графа с n³ 3,
обхват которого равен h[k1] ³[k2] 3, верно неравенство m(h — 2)£
£h(n — 2). Используя это соотношение, докажите, что граф Пе-
терсена непланарен.

14. Убедитесь, что реберные графы графов К₅ и K_3,3 не-
планарны.

15. Какие из графов, изображенных на рис. VI.1, являются
планарными?

16. При каких n графы порядка 2n, изображенные на рис. VI.2,
являются планарными?

17. Изобразите стереографические проекции пяти платоно-
вых тел.

18. Докажите, что не существует плоского графа с пятью гра-­
нями, обладающего тем свойством, что любые две его грани имеют
общее ребро.

19 Пусть G — плоский двусвязный граф. Докажите, что мно-­
жество всех простых циклов, каждый из которых ограничивает
внутреннюю грань графа G (см. теорему 37.7), образует базис цик-­
лов графа G.

20.Планарный граф называется внешнепланарным, если его
можно уложить на плоскости так, что все его вершины будут ле­
жать на границе одной грани (удобно в качестве такой грани брать
внешнюю грань). Докажите, что следующие утверждения экви­
валентны:

1) граф G внешнепланарен;

2) граф G', полученный из G добавлением новой вершины и
соединением ее новыми ребрами со всеми вершинами графа G,
планарен;

3) каждый блок графа G внешнепланарен.

21. Внешнепланарный граф называется максимальным внешне­
планарным, если он перестает быть внешнепланарным при добав­
лении любого ребра. Пусть в таком графе число вершин n ³3 и

все они лежат на границе внешней грани. Покажите, что тогда граф имеет n — 2 внутренние грани.

22. Докажите, что любой максимальный внешнеплапарный
граф G с n³3 вершинами имеет а) 2n — 3 ребра; б) по крайней
мере две вершины степени 2; в) x(G) = 2.

23. Какое минимальное число ребер (вершин) необходимо уда­
лить из куба Q₄, чтобы полученный граф стал планарным?

24. Докажите изоморфизм графов, изображенных на рис. VI.3.
Изоморфны ли графы, геометрически двойственные к ним?

25. Пусть плоский граф G не связен. Покажите, что тогда его
«второй геометрически двойственный» граф G** не изоморфен
графу G.

26. Покажите, что граф, геометрически двойственный к коле­
су W_n, является колесом.

27. Пусть планарный (n,m)-граф G таков, что двойственный
к нему изоморфен графу G. Покажите, что тогде т = 2n — 2.

28. Покажите, что планарный граф (без петель) является
2-связным тогда и только тогда, когда двойственный к нему
2-связен.

29. Найдите графы, геометрически двойственные к стереогра­-
фическим проекциям Платоновых тел.

30. Воспользовавшись алгоритмом Y укладки графа на плос­-
кости, покажите, что граф К₅ не планарный.

31. С помощью алгоритма Y постройте плоские укладки или
установите непланарность графов, изображенных на рис. VI.4.

32. Чему равна искаженность графов К₅ К_3,3и графа Пе-
терсена?

33. Чему равно число скрещиваний графов К₅, Кз.з и графа
Петерсена?

34. Докажите или опровергните утверждение: сг(С) = 1 для непланарного графа G тогда и только тогда, когда существует та­кое ребро е. что граф G — е планарен.

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

36. Найдите толщину графов К₅, К_3,3 и графа Петерсена. 37. Покажите, что всякий непланарный граф гомеоморфен не­которому графу толщины 2.

38. Уложите куб Q₄ на торе.

39. Найдите род графа Петерсена.

40. Приведите пример графа рода 2.

41. Покажите, что род графа не превосходит числа скрещива­ний, т. е. Y(G)£cr(G). Приведите примеры графов G, для кото­рых 1) Y(G) < сг(G), 2)Y(G) =.cr(G).

42. Покажите, что не существует полного графа рода 7.

43. Можно ли уложить графы К₅ и К_3,3 на листе Мёбиуса?

[k1]

[k2]