На карте точками обозначены города, а линиями - дороги. Какое наименьшее число дорог нужно добавить, чтобы из городов выходило поровну дорог?

1. Понимание условия

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

2. Анализ рисунка

На рисунке изображён граф с 9 вершинами.
Нужно определить степени вершин в текущем графе.

Посчитаем степени (количество рёбер, выходящих из вершины):

• Верхний ряд (слева направо): 1, 3, 2
• Средний ряд: 3, 4, 3
• Нижний ряд: 2, 3, 1

Проверим:
Вершина 1 (левый верхний угол): соединена с вершиной 2 (рядом справа)...