ISRO CS 2025 Q.5: solution and answer

Official answer: ASource: ISRO's final answer key of 15 May 2026

1. Model the road map as a graph. Each shopping mall is a vertex and each road is an edge. The malls are interconnected, so the graph is connected. Roads do not cross, so the graph is drawn in the plane with no crossings: it is a connected planar graph. So $V=20$, and each mall is reached by 3 roads, so every vertex has degree 3.

2. Handshake lemma: $\sum \mathrm{deg}(v)=2E$, so $2E=20\times 3=60$ and $E=30$.

3. A planar drawing divides the plane into regions (faces), each bordered by roads. Euler's formula for a connected planar graph gives the number of regions: $$V-E+F=2\Rightarrow F=2-V+E=2-20+30=12.$$ This holds for every crossing-free layout of such a road network, so the number of regions is always 12.

4. The roads mark off exactly these 12 regions, and the outer region is one of them: it is separated from every other region by roads, and no road runs through it. A concrete layout makes this clear. The dodecahedron's edge graph has 20 vertices of degree 3 and 30 edges; drawn flat, it shows 11 pentagonal regions inside and the outer region, which is the dodecahedron's twelfth face. On the solid all 12 faces are alike, so the outer region of the flat drawing is a region bordered by roads just like the others.

5. Only one park goes in a region, and a park cannot sit on a road, so each park takes a region of its own. Hence the maximum number of parks equals the number of regions, $F=12$.

6. Options (b) 30 and (c) 60 are $E$ and $2E$, an edge count and a degree sum, not region counts. Option (d) 11 leaves out the outer region. The answer is (a), 12.