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

В графе сумма степеней всех вершин равна удвоенному числу рёбер, поэтому она должна быть чётной.

В требуемом графе сумма степеней равна \(3\cdot3+5\cdot4=9+20=29\), то есть нечётна. Это противоречит свойству графа.

Ответ: невозможно.