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

По лемме о рукопожатиях сумма степеней всех вершин графа должна быть чётной:

\(1+2+3+4+5+6+7=28\).

Поэтому степень восьмой вершины должна быть чётной. Но проверим существование такого простого графа.

Вершина степени 7 соединена со всеми остальными вершинами. Вершина степени 1 уже соединена с ней и больше ни с кем соединяться не может. После удаления этих двух вершин степени оставшихся пяти заданных вершин равны \(5,4,3,2,1\), а степень восьмой вершины уменьшается на 1.

Перебор возможных чётных степеней \(0,2,4,6\) приводит к невозможным наборам степеней: при \(0\) вершина не может быть соединена с вершиной степени 7, а при \(2,4,6\) нарушается условие существования простого графа после последовательного удаления вершин максимальной степени.

Ответ: такого простого графа не существует, поэтому степень восьмой вершины определить нельзя.