Теорема 5. Пусть p – число вершин, q – число ребер, r – число граней правильного многогранника. Тогда возможен один из следующих случаев, рассмотренных в таблице 4.1.

Таблица 4.1

Свойства тел Платона

	p	q	r
Тетраэдр	4	6	4
Куб	8	12	6
Октаэдр	6	12	8
Додекаэдр	20	30	12
Икосаэдр	12	30	20

Доказательство. Вершины графа, состоящего из ребер и вершин фиксированного многогранника имеют одинаковую степень. Обозначим эту степень черезx. Пустьy– число сторон грани этого многогранника. Получаем систему уравнений

.

Так как x,y3, а в случаеx,y4 имеет место неравенство, то возможны следующие случаи:x=3 илиy=3.

Рассмотрим случай x=3:

.

Получаем

x=3,y=3,;

x=3,y=4,;

x=3,y=5,.

Аналогично x=4 ,x=5 приy=3.

4.7. Упражнения Свойства графов

Все графы предполагаются простыми. Графы называются изоморфными,

если существует биекция fмежду множествами их вершин, такая что

{u,v}ребро{f(u),f(v)}– ребро.

1. Доказать, что граф имеет четное число вершин с нечетными степенями.

2. При встрече студентов состоялось 15 рукопожатий, трое человек сделали по 4 рукопожатия, а другие – по 3. Сколько было студентов.

3. Может ли существовать группа из 23 человек, каждый из которых знаком с пятью другими?

4. В соревнованиях по шахматам по круговой системе участвуют 5 человек. Все, кроме Иванова и Петрова, сыграли различное число партий. Сколько партий сыграли Иванов и Петров?

5. Можно ли нарисовать без отрыва карандаша граф K₆, у которого удалено одно ребро.

6. Найти число попарно неизоморфных графов, у которых 2 вершины имеют степень 2, 2 вершины имеют степень 3, и 2 вершины имеют степень 4. Остальные вершины имеют степень 0.

7. Найти число попарно неизоморфных графов, у которых 3 вершины имеют степень 2, 3 вершины имеют степень 3, и 3 вершины имеют степень 4. Остальные вершины имеют степень 0.

8. Доказать, что в простом графе, имеющем не меньше двух вершин, всегда найдутся две вершины одинаковой степени.

9. Какие из графов, приведенных на рис. 4.12 , изоморфны?

Рис. 4.12. Примеры графов

10. Какие из графов, приведенных на рис. 4.13 , изоморфны?

Рис. 4.13. Примеры графов

11. Найти число всех попарно неизоморфных графов, имеющих 4 вершины. Нарисовать эти графы.

Ответ: существует 11 неизоморфных графов (рис.4.14).

Рис. 4.14. Графы, имеющие 4 вершины

12. Кратчайший путь, соединяющий вершины uиvв графе, называетсягеодезическим путеммежду вершинами. Его длина обозначаетсяd(u,v). ДиаметромD()графа называется длина самого длинного геодезического пути в этом графе, т.е.D()=max{d(u,v) :u,v V}. Найти диаметр графа, приведенного на рис. 4.15. Найти диаметр графаK₅.

Рис. 4.15. Пример графа

13. Матрица смежности состоит из коэффициентов a_ij=1вершиныiиjсмежны.

(1) Построить матрицы смежности для графов K₃иK₄;

(2) Доказать, что сумма коэффициентов i-й строки матрицы смежности равна степениi-й вершины;

(3) Построить матрицу смежности графа, состоящего из вершин и ребер куба.

(4) С помощью матрицы смежности построить матрицу, коэффициентами которой является количества путей длины 2 из вершины iв вершинуj.

(5) Как связаны след матрицы A³с числом треугольников в графе?

14. Циклы {z₁, z₂,    , z_n}называютсянезависимыми, если z₁z₂    z_n  Доказать, что у связного графа максимальное число независимых циклов равноq-p+1.

15. Сколько компонент связности имеет лес, содержащий 76 вершин и 53 ребра?

16. Доказать, что среди 6 человек найдется тройка знакомых, или тройка незнакомых людей.

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