Problem

Source: IX International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade

Tags: graph theory, combinatorics



Some of the towns in a country are connected with bidirectional paths, where each town can be reached by any other by going through these paths. From each town there are at least $n \geq 3$ paths. In the country there is no such route that includes all towns exactly once. Find the least possible number of towns in this country (Answer depends from $n$).