Topic: Discrete Mathematics / Graph Theory
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
Answer: D. 11
Explanation: This can be modeled as a planar graph where malls are vertices ($V$) and roads are edges ($E$).
Number of vertices, $V = 20$.
Degree of each vertex = 3.
Total number of edges, $E = \frac{V \times \text{degree}}{2} = \frac{20 \times 3}{2} = 30$.
Using Euler's formula for a connected planar graph: $V - E + F = 2$, where $F$ is the total number of faces (regions).
$20 - 30 + F = 2 \implies F = 12$.
This $F$ includes 1 unbounded (outer) region and 11 bounded regions. The parks are to be constructed in regions strictly "enclosed by roads" (the bounded faces), which is $F - 1 = 11$.