В некоторой стране имеется n городов. Города соединяются непересекающимися между собой дорогами. Из каждого города выходят ровно три дороги, по которым из города можно выехать и соответственно, въехать. Все дороги в стране пронумерованы цифрами 1, 2 и 3 так, что из каждого города выходят дороги с тремя различными номерами 1, 2, 3. Докажите, что такая конфигурация дорог возможна только при четном числе n. Для произвольного четного n постройте пример расположения городов и дорог.
Обозначим - количество дорог, соединяющих города. Так как из каждого города выходит ровно три дороги, то - количество всех дорог, умноженное на 2. То есть, . Следовательно, n четное.
Пример Пусть на плоскости изображен выпуклый угольник (при четном ). Пронумеруем его вершины числами , а стороны последовательно цифрами . Соединим отрезками вершины с номерами и при . Эти отрезки пронумеруем цифрой 3. Остается соединить дорогой с номером 3 вершины 1 и (см. рис.)
