A University Police Department had decided to install emergency telephones at select locations on campus. The department wants to install the minimum number of telephones so that each street has at least one phone covering it. The figure below maps the principal streets (A to K) on campus. It is logical to place the telephones at intersections of streets so that each telephone will serve at least two streets. For example, Location 2 provides coverage for Streets A, B, D and E according to the figure below, which shows the layout of the streets and the telephone locations (encircled numbers).

Let xj = 1 if a telephone is installed in location j

and xj = 0 if a telephone is NOT installed in location j

If location 4 becomes unavailable, which of the following locations MUST have a telephone installed?

Both 2 and 5

7

5

All of 2, 5 and 7

2

PreviousNext