Решение задачи 335

Условие:

В стране 10 городов. Возможно ли проложить между городами дороги так, чтобы из каждого города выходило по 3 дороги и из каждого города в каждый можно было бы добраться по дорогам, заходя не более, чем в один промежуточный город?

Решение:

Назовём пересадкой путь, проходящий через промежуточный город.

Рассмотрим какой-то город (красный). Из него выходят 3 дороги в какие-то другие города (синие). Заметим, что из синих городов должны выходить ещё по 2 дороги в различные зелёные города, т.к. иначе в какой-то из зелёных городов нельзя было бы попасть из красного с не более чем одной пересадкой.

Таким образом, на данном этапе мы имеем 🌲. Из каждого зелёного города должны выходить ещё по 2 дороги в зелёные города.

Зеленые вершины объединены по парам со своим родителем (на рисунке пары обведены оранжевым).

Предположим, что есть ребро, соединяющее две зелёные вершины в одной паре (самой левой). Тогда найдется пара других зелёных вершин, к которую не будет проведено ребро из первой пары (самая правая). Это означает, что напрямую из вершины первой пары нельзя добраться в вершину третьей пары. Значит можно добраться не менее, чем с одной пересадкой. Это означает, что до родителя третьей пары (он выделен синим цветом) из вершины первой пары можно добраться минимум с двумя пересадками, что запрещено условием.

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

Теперь почти однозначно можно получить требуемый пример. Проверьте его правильность!

Ответ: да, возможно.