В5. а) Докажите, что не существует графа без кратных рёбер и петель, у которого 8 вершин, степени которых равны 8, 7, 6, 5, 4, 3, 2, 1. б) Нарисуйте какой-нибудь граф, у которого 8 вершин, степени которого равны 8, 7, 6, 5, 4, 3, 2, 1.

а) Доказательство несуществования графа: Сумма степеней всех вершин в графе должна быть четным числом, поскольку каждое ребро соединяет две вершины и, следовательно, вносит вклад в сумму степеней дважды. В данном случае сумма степеней вершин равна 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36, что является четным числом. Однако, вершина со степенью 7 должна быть соединена со всеми остальными 7 вершинами. Вершина со степенью 8 невозможна в графе с 8 вершинами без петель и кратных ребер (максимальная степень 7). Следовательно, такого графа не существует. б) Невозможно нарисовать граф с указанными степенями, так как вершина со степенью 8 невозможна без петель и кратных ребер.