Задача 2:

Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.

Решение:

Поскольку из всех вершин, кроме одной выходит по 4 ребра, то и из пятой вершины также должно выходить четыре ребра.

Задача 3:

Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, …, n, n.

Решение:

Используйте индукцию по n.

Задача 4:

Верно ли, что два графа изоморфны, если

а) у них по 10 вершин, степень каждой из которых равна 9?

б) у них по 8 вершин, степень каждой из которых равна 3?

в) они связны, без циклов и содержат по 6 ребер?

Решение:

а) Верно. Каждая вершина соединена с каждой.

б) Нет

в) Нет

Задача 5:

В связном графе степени четырех вершин равны 3, а степени остальных вершин равны 4. Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.

Решение:

Если это ребро соединяет вершины с одинаковыми степенями, то в каждой компоненте нечетное число нечетных вершин. В противном случае только в одной компоненте будет вершина степени 2.