Сириус. Комбинаторика. 7 класс. Введение в графы

Вася выписал в ряд степени всех вершин графа. Какие наборы чисел он мог написать?

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, что невозможно

Остальные задачи раздела