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

Решение:

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

В данном случае у нас 8 городов (вершин).

Степень трёх городов = 3.

Степень пяти городов = 4.

Сумма степеней вершин = \( 3 × 3 + 5 × 4 = 9 + 20 = 29 \).

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

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

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