Упражнения

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 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 внешнепланарен;

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

2. каждый блок графа 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 — е планарен.

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

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 на листе Мёбиуса?