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

Решение:

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

3 города * 5 дорог/город + 4 города * 3 дороги/город = 15 + 12 = 27.

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

Следовательно, построить такой граф невозможно.

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