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