OSN 2011 Problem 4

An island has $10$ cities, where some of the possible pairs of cities are connected by roads. A tour route is a route starting from a city, passing exactly eight out of the other nine cities exactly once each, and returning to the starting city. (In other words, it is a loop that passes only nine cities instead of all ten cities.) For each city, there exists a tour route that doesn't pass the given city. Find the minimum number of roads on the island.