# Trip Routes that Visit 9 of 10 Cities

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.

• "goes to 8 of 9 other cities exactly" means from A you should have a connection between one of the cities? or it is at least 8?
– Oray
Feb 22, 2018 at 14:14
• If the cities are labeled 1 to 10, then a cycle of 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 1 is an example of a trip route that doesn't visit 4. Feb 22, 2018 at 14:29

15

After playing around with it I realized that each city must have at least 3 paths so that if one city goes down there are still 2 paths to enter and leave the city.

Then I tried to construct the cities such that each city ONLY has 3 paths, the minimum required.

Although I am unable to provide a mathematical proof.

• You have a mathematical proof in your answer: there can't be a city with less than 3 roads to it! so you have a minimum number, as you have shown this minimum is doable, you have your demonstration. Feb 22, 2018 at 14:11
• This is called graph theory. It's a really interesting part of math. Feb 22, 2018 at 14:14
• "goes to 8 of 9 other cities exactly",
– Oray
Feb 22, 2018 at 14:14
• Also, because your graph is vertex-transitive, just showing one 9-city tour shows that any city can be the one left out of the tour. Feb 22, 2018 at 18:35
• @athin Unless there's only 3 cities, in which case you only need 2 paths :^) Feb 23, 2018 at 13:45