GATE CS 2015 Set 1 Q54 — Graphs: Connectivity, Matching, Colouring

We are given:

• Number of vertices, $V = 10$
• Each face is bounded by exactly $3$ edges (i.e., the degree of each face is $3$).

Let $E$ be the number of edges and $F$ be the number of faces in the connected planar graph $G$.

1. Relation between Edges and Faces

Since every edge is shared by exactly two faces, the sum of the boundary lengths (degrees) of all faces is equal to twice the number of edges:

Since each face is bounded by exactly $3$ edges:

2. Applying Euler's Formula

For any connected planar graph, Euler's formula states:

Substituting $V = 10$ and $F = \frac{2E}{3}$ into the formula:

Thus, the number of edges in $G$ is 24.