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

Нет, это невозможно.

Сумма степеней всех вершин графа должна быть четной, т.к. равна удвоенному числу ребер. В данном случае сумма степеней равна 3 * 3 + 5 * 4 = 9 + 20 = 29, что является нечетным числом. Следовательно, построить такой граф невозможно.

Ответ: Невозможно, т.к. сумма степеней нечетная.