Эти задания могут помочь при подготовке к экзамену. И это уже больше похоже на то, что будет в экзамене =)
1. Построить произвольный связный ациклический граф на 13 вершинах, имеющий следующее распределение степеней вершин: 2 вершины степени 4, 1 вершина степени 2 и 8 вершин степени 1; или дать обоснованный ответ о невозможности построения такого графа.
2. Определить все возможные значения хроматического числа графов на 17 вершинах, цикломатическое число которых не превосходит 2.
3. Определить все возможные значения диаметров графов, имеющих 19 вершин и не более 18 ребер.
4. Не проводя раскраски, найти точное значение хроматического числа.
5. Проверить, существует ли среди связных графов, имеющих 6 вершин и 9 ребер, Эйлеров граф? Если существует, указать его. В противном случае дать обоснование его отсутствия.
6. Найти все компоненты сильной связности для заданного графа. Компоненты задать перечислением вершин.
7. Построить группу автоморфизмов для заданного графа. Для каждого автоморфизма (подстановки) указать обратный автоморфизм (обратную подстановку).
8. Для заданного графа вычислить число внутренней устойчивости.
9. Построить произвольный связный граф на 13 вершинах, минимальная вершинная связность которого не менее 5, а минимальная степень вершин не более 4, или дать обоснованный ответ о невозможном построении такого графа.
10. Определить все возможные значения хроматического числа для связных графов на 72 вершинах, цикломатическое число которых не превосходит 2.
11. Определить цикломатическое и хроматическое число в графе
, где 
и 
– полные графы на 10 и 15 вершинах,
– простой цикл на 8 вершинах, причем графы и имеют одну общую вершину.
12. Вычислить число внешней устойчивости графа 
, где 
– простой цикл на 5 вершинах, 
– полный граф на 77 вершинах, при этом и имеют одну общую вершину.
13. Определить плотность графа.
14. Найти точную раскраску графа.
15. Определить цикломатическое и хроматическое числа в графе
, где 
– полный двудольный граф на 10 и 15 вершинах соответственно, у которого удалено два смежных ребра, 
– простой цикл на 4 вершинах, причем графы не имеют общих вершин.
16. Определить цикломатическое и хроматическое числа в графе
, где – полный двудольный граф на 10 и 15 вершинах соответственно, у которого удалено два смежных ребра, – простой цикл на 4 вершинах, причем графы имеют одну общую вершину.
17. Проверить, обладает ли граф свойством реберности. Если да, найти его образ.
18. Для заданного графа указать любые две вершины, расстояние между которыми максимально. Указать значение этого расстояния.
19. Указать все связные графы на 5 вершинах, группа автоморфизмов которых содержит подстановку 
20. Построить произвольный связный граф на 13 вершинах, вершинная связность которого не менее 4, реберная связность рана 5, а минимальная степень вершин не более 4, или дать обоснованный ответ о невозможности построения такого графа.
21. Построить произвольный двудольный связный граф на 12 вершинах, который имеет следующее распределение вершин: 1 вершина степени 4, 3 вершины степени 3, 3 вершины степени 2 и 5 вершин степени 1, или дать обоснованный ответ о невозможности построения такого графа.
