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

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

Пример объяснения:

• Предположим, что такой граф существует.
• Тогда сумма степеней всех вершин равна 3 * 3 + 5 * 4 = 29.
• Но сумма степеней всех вершин должна быть чётной, так как каждое ребро вносит вклад 2 в общую сумму.
• Получаем противоречие, следовательно, такой граф невозможен.