A tour route not passing the chosen city for every city
Source: Indonesian Mathematics Olympiad 2011, Day 1, Problem 4
September 13, 2011
symmetrypigeonhole principleceiling functiongraph theorycombinatorics proposedcombinatorics
Problem Statement
An island has 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.