GATE CS 1992 Q02 — Graphs: Connectivity, Matching, Colouring

According to Kuratowski's Theorem, a graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ (the complete graph on $5$ vertices) or $K_{3,3}$ (the complete bipartite graph on $6$ vertices).

Let's determine the minimum number of vertices required for a graph to be non-planar:

1. Graphs with $v \le 4$ vertices: All such graphs are planar. The complete graph $K_4$ has $4$ vertices and is planar.
2. Graphs with $v = 5$ vertices: For any simple planar graph with $v \ge 3$ vertices, the maximum number of edges is given by: $$e_{\max} = 3v - 6$$ For $v = 5$: $$e_{\max} = 3(5) - 6 = 9$$ This means any graph with $5$ vertices and $9$ or fewer edges can be planar.
   However, the complete graph $K_5$ has $5$ vertices and: $$e = \frac{5 \times 4}{2} = 10 \text{ edges}$$ Since $10 > 9$, $K_5$ is non-planar.

Thus, the non-planar graph with the minimum number of vertices is $K_5$, which has $5$ vertices and $10$ edges.