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

Обозначим количество городов с 5 дорогами как $$n_5 = 3$$, а количество городов с 3 дорогами как $$n_3 = 4$$. Общее количество вершин $$n = n_5 + n_3 = 3 + 4 = 7$$.

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

Сумма степеней вершин: $$S = n_5 \cdot 5 + n_3 \cdot 3 = 3 \cdot 5 + 4 \cdot 3 = 15 + 12 = 27$$.

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

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