Докажите, что количество дорог не превосходит...

[Betrugerin]

"В стране n городов и некоторые из них соединены дорогами. Известно, что в стране нет ни одного замкнутого несамопересекающегося маршрута длины 4. Докажите, что количество дорог не превосходит $(n-1)^2/4$."
Натолкните, пожалуйста.

[diana_yatsenko]

Начертите на бумаге n-угольник - граф. Соедините вершины и проделайте ориентацию ребер. Пересечений нет - имеете планарный граф, далее вводите условие задачи в отношении ребер графа.