Question 10
Beaverland has 12 cities connected by highways A–O, as shown.
A group of cities is an economic community if any two cities in it are connected directly, or by a route through other cities in the same group. All 12 cities initially form one community. Because of a Covid-19 outbreak, the mayors decide to block exactly two highways to divide the country into three separate communities. To reduce economic disruption, they want the smallest resulting community to contain as many cities as possible. They find an optimal choice. How many cities are in the smallest community?
A group of cities is an economic community if any two cities in it are connected directly, or by a route through other cities in the same group. All 12 cities initially form one community. Because of a Covid-19 outbreak, the mayors decide to block exactly two highways to divide the country into three separate communities. To reduce economic disruption, they want the smallest resulting community to contain as many cities as possible. They find an optimal choice. How many cities are in the smallest community?