3. Можно ли соединить 8 городов дорогами так, чтобы из трёх городов выходило по три дороги, а из оставшихся пяти городов по четыре дороги? Нарисуйте пример подходящего графа или объясните, поче му это невозможно.

Решение:

Для решения этой задачи используем понятие суммы степеней вершин графа. Сумма степеней всех вершин графа должна быть равна удвоенному количеству ребер (так как каждое ребро учитывается дважды).

В нашем случае есть 3 города с 3 дорогами и 5 городов с 4 дорогами. Сумма степеней будет:

Так как сумма степеней должна быть четной (удвоенное количество ребер), а 29 - нечетное число, то построить такой граф невозможно.