Упражнения для самостоятельного решения
1. Сколько всего: а) связных графов на множестве из 3 вершин; б) неизоморфных графов на множестве из 4 вершин? Ответ: а) 2; б) 11.
2. Сколько всего неизоморфных деревьев с 6 вершинами? Ответ: 6.
3. Сколько всего неизоморфных графов, имеющих 10 вершин, а количество рёбер равно: а) 45; б) 44; в) 43? Ответ: а) 1; б) 2; в) 2.
4. Сколько компонент связности может иметь граф, у которого 12 вершин и 40 рёбер? Ответ: 1,2,3.
5. Построить матрицу смежности и матрицу инцидентности графов, изображённых на рисунке.
Ответ: а) 
6. Изобразить граф, имеющий следующую матрицу смежности: а) 
б) 
Ответ:
7. Изобразить граф, имеющий следующую матрицу инцидентности: а) 
б) 
Ответ:
8. Является ли связным граф со следующей матрицей смежности: 
Ответ: нет.
9. Существует ли граф со следующим набором степеней вершин: а) 1,1,1,2,2,3,3; б) 1,1,2,2,2,3,3,4? Ответ: а) нет; б) да.
10. Пусть 
– граф. Противоположным графом назовём граф 
с тем же множеством вершин, что и у 
причём 
Доказать, что если граф несвязный, то граф связный.
11. Доказать, что граф с 
вершинами, имеющий более 
рёбер, является связным.
12. Построить двоичный код дерева (начало обхода помечено крестиком и стрелкой):
Ответ: (0010100101001111).
13. Построить код Прюфера дерева
Ответ: [2343311].
14. Построить дерево по его двоичному коду: (0010010010111011).
Ответ:
15. Построить дерево по его коду Прюфера: [2442778].
Ответ:
16. Построить базис пространства циклов графа, изображённого на рисунке.
Ответ: 
(ответ неоднозначен).
17. 
В графе 
рассмотрим цикл 
Дополнить его до базиса пространства циклов. Ответ: например, так: 
18. Чему равна размерность пространства циклов графа 
Сколько в 
всего обобщённых циклов? Ответ: 6; 64.
19. Сколько компонент связности имеет лес, у которого 25 вершин и 11 рёбер? Ответ: 14.
20. Сколько граней имеет планарный граф, у которого 12 вершин и 30 рёбер? Ответ: 20.
21. Являются ли планарными графы: а) 
б) 
Ответ: а) да; б) нет.
22. Граф представляет собой трёхмерный куб, в котором проведена диагональ. Планарен ли этот граф? Ответ: нет.
23. Сколько рёбер следует удалить из графа 
чтобы получилось дерево? Ответ: 25.
24. Чему равно наименьшее количество рёбер, удаление которых из графа 
делает граф несвязным? Ответ: 5.
25. Чему равно наименьшее число 
обладающее свойством: удаление из графа любых 
рёбер делает граф несвязным? Ответ: 26.
26. Связный планарный граф без петель, висячих вершин и кратных рёбер имеет 6 вершин. Сколько рёбер может иметь этот граф? Ответ: 
27. Связный планарный граф без петель, висячих вершин и кратных рёбер имеет 5 вершин. Сколько граней может быть в его плоской укладке? Ответ: 
28. Связный планарный граф без петель и висячих вершин имеет 19 рёбер. Сколько граней может быть в его плоской укладке? Ответ: 
29. Найти хроматическое число графа, изображённого на рисунке
Ответ: а) 3; б) 4.
30. Найти рёберное хроматическое число следующих графов: а) 
б) 
в) состоит из вершин и рёбер октаэдра. Ответ: а) 3; б) 4; в) 5.
31. Верно ли, что 
Ответ: да.