CEMC Banner

Problem of the Week
Problem C
Building Community

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.

A description of the diagram follows.

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.

  1. If the mayor chooses to build five community centres, which five towns could the mayor choose?

  2. 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.

Theme: Computational Thinking