ISRO CS 2023 Q.43: solution and answer

ISRO 2023 · CSQ.43 · 1 mark · MCQ

If there are five faces and nine vertices in an undirected planar graph, then number of edges is

(A)
14
(B)
16
(C)
12
(D)
None of the above

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The graph has $12$ edges, which is option (c).

Official answer: CSource: ISRO's revised and final answer key of 16 February 2024

For a connected planar graph, Euler's formula relates vertices, edges and faces: $V - E + F = 2$ . The question treats the graph as connected, which is the standard reading.
Substitute $V = 9$ and $F = 5$ : $9 - E + 5 = 2$ .
Solve for $E$ : $E = 9 + 5 - 2 = 12$ .
Check against the options: with $V = 9$ , the formula gives $F = E - 7$ . So $E = 14$ would give $F = 7$ faces and $E = 16$ would give $F = 9$ faces, neither of which is 5. Only $E = 12$ gives $F = 5$ , so option (c) is correct and (d) does not apply.

KEY IDEA

Euler's formula for a connected planar graph, $V - E + F = 2$ , gives the missing count when two of the three are known. The outer (unbounded) region counts as a face.

WATCH OUT FOR

Using $V - E + F = 1$ (which gives $E = 13$ ), or writing $V + E - F = 2$ and mixing up the signs. Another slip is forgetting that the outer region counts as one of the faces.

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 4 ISRO Graph theory questions, with notes

ISRO CS 2023 Q.43: solution and answer

Answer and solution

More ISRO Graph theory questions