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

Рассуждение:

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