An island contains twelve small towns that are connected by roads as shown in the diagram below. The towns are labelled with the letters A through L and the roads connecting the towns are indicated by line segments.
The mayor of the island is going to build community centres in some of the towns so that each town either has its own community centre, or is connected by a single road to a town that has a community centre.
If the mayor chooses to build five community centres, which five towns could the mayor choose?
What is the fewest number of community centres the mayor needs to build?
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
There are many possible answers. Two possibilities are shown below, where the chosen towns are circled.
There are two towns that have only one road leading out of them, namely towns \(A\) and \(E\). Since each town must either have its own community centre or be connected by a single road to a town that has a community centre, we need to put one community centre in town \(A\) or \(B\), and another community centre in town \(E\) or \(F\). Since towns \(B\) and \(F\) are connected to other towns as well, they are the better choices if we want to build the fewest number of community centres.
After choosing towns \(B\) and \(F\), the remaining towns that don’t have their own community centre and are not connected by a single road to a town that has a community centre are towns \(G\), \(H\), \(J\), \(K\), and \(L\). None of these five towns are connected to all the others, and there is no town that is connected to all five of the towns. So we need at least two more community centres to cover the remaining five towns. Choosing towns \(K\) and \(H\) would work.
Therefore, the fewest number of community centres the mayor needs to build is four.
Note that this is not the only group of four towns that we could have chosen. There are several other possibilities.