There are 20 shopping malls in a city interconnected by roads. Each shopping…
2025
There are 20 shopping malls in a city interconnected by roads. Each shopping mall can be reached through 3 different roads. It is assumed that:
Only one park is planned to be constructed in a region
Roads do not cross each other
Road(s) do not pass through a park.
What is the maximum number of parks that can be constructed in the regions enclosed by roads?
- A.
12
- B.
30
- C.
60
- D.
11
Attempted by 47 students.
Show answer & explanation
Correct answer: D
First, calculate the number of edges using the Handshaking Lemma. With 20 vertices each having degree 3, the sum of degrees is 60, meaning there are 30 edges. Next, apply Euler's formula for planar graphs: V - E + F = 2. Substituting the values gives 20 - 30 + F = 2, resulting in a total of 12 faces. Finally, since the question asks for regions enclosed by roads (bounded regions), subtract the one outer infinite face from the total faces. Thus, 12 - 1 = 11 parks can be constructed.