Вася выписал в ряд степени всех вершин графа. Какие наборы чисел он мог написать?
1. 9, 8, 8, 7, 6, 6, 3, 2, 1
Всего 9 вершин, значит степени 9 быть не может
2. 8, 8, 7, 7, 6, 5, 4, 2, 1
Первая вершина соединена со всеми остальными и вторая тоже. Значит не может быть вершины со степенью 1. Минимум 2.
3. 8, 7, 6, 5, 4, 4, 3, 2, 1
Первая вершина соединена со всеми, последняя (9я) только с первой.
Вторая со всеми, кроме девятой. Восьмая с первой и второй.
Третья в связи со всеми, кроме 9й и 8й. Седьмая с первой, второй и третьей.
Четвертая со всеми, кроме 9, 8 и 7. Пятая и шестая уже получили по 4 степени.
4. 8, 7, 5, 4, 4, 3, 2, 2, 2
Сумма степеней равна 37, что невозможно
