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

Решение:

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

В нашем случае:

• Есть 7 городов (вершин).
• 3 города имеют степень 5.
• 4 города имеют степень 2.

Сумма степеней вершин = \(3 \times 5 + 4 \times 2 = 15 + 8 = 23\).

Согласно теореме, эта сумма должна быть чётным числом (удвоенное число рёбер). Однако, 23 — нечётное число.

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

Ответ: Невозможно. Сумма степеней вершин графа (23) нечётная, что противоречит теореме о рукопожатиях.