Задание 2. В графе 6 вершин. Степени вершин равны: 5, 3, 3, 2, 2, 1. а) Возможно ли существование такого графа? Обоснуйте ответ. б) Если да — найдите число рёбер.

а) Да. Покажем, что последовательность степеней реализуема. Вершина степени 5 соединена со всеми остальными; после этого степени остальных вершин уменьшаются на 1, и получаем последовательность 2, 2, 1, 1, 0. Её можно реализовать: соединить вершины степеней 2 друг с другом и с одной вершиной степени 1; вторую вершину степени 1 соединить с первой вершиной степени 2. Тогда степени равны 2, 2, 1, 1, 0.

б) Сумма степеней равна 5 + 3 + 3 + 2 + 2 + 1 = 16. Каждое ребро учитывается при подсчёте степеней дважды, поэтому число рёбер равно 16 : 2 = 8.

Ответ: такой граф существует; в нём 8 рёбер.