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

Пусть есть 7 городов. Обозначим их количество как `n = 7`. Пусть 3 города имеют степень 5, а 4 города имеют степень 3.

Сумма степеней всех вершин графа должна быть равна удвоенному числу ребер (лемма о рукопожатиях). То есть, сумма степеней должна быть четным числом.

Сумма степеней в нашем случае:

$$3 \times 5 + 4 \times 3 = 15 + 12 = 27$$

Так как 27 - нечетное число, то построить такой граф невозможно. Сумма степеней вершин графа должна быть четной.

Ответ: Невозможно соединить 7 городов указанным образом, так как сумма степеней вершин (27) является нечетным числом.