There are 10 cities on this island. For each pair of cities, they may have a bidirectional path.
A trip route is defined as a route which start on a city e.g. $A$, goes to 8 of 9 other cities exactly once (by the paths), and goes back to city $A$. (i.e. a trip route is a cycle of 9 cities/paths.)
What is the minimum number of the paths on this island; so that for each city, there exist a trip route that doesn't visit it?
This puzzle is taken from Indonesia National Science Olympiad in Mathematics 2011.